Record
Craft
Prob. 1
有想法。
printf( "nan" );
Prob.2
没读懂
Prob. 3
定义 (f_{i,j,0/1}) 表示个寂寞。
[f_{i,i,0/1}=|a_{i}| imes I
]
[f_{i,j,0}=min{f_{i+1,j,0}+(a_{i+1}-a_{i}) imes(I-j+i),f_{i+1,j,1}+(a_{j}-a_{i}) imes(I-j+i)} \f_{i,j,1}=min{f_{i,j-1,1}+(a_{j}-a_{j-1}) imes(I-j+i),f_{i,j-1,0}+(a_{j}-a_{i}) imes(I-j+i)}
]
[mathrm{ANS}=max{i imes m-min{f_{l,r,0/1}}}
]
Over.
Prob. 4
转化一下，把 ( exttt{C,T}) 换成左括号和右括号。
把左括号赋值为 (1)，右括号 (-1)。
把这个 (1/-1) 序列设为 (A)
那么所有前缀中 ( exttt{C}) 的个数大于等于 ( exttt{T}) 的个数即要求前缀和不能出现负数。
询问即求：定义 (P_{i}=sum_{j=1}^{i}A_{j},S_{i}=sum_{j=i}^{n}A_{j})，对于每次询问回答：
[egin{cases}0,min{min{P_{l,l+1,cdots,r}},min{S_{l,l+1,cdots,r}}}ge0 \ |min{min{P_{l,l+1,cdots,r}},min{S_{l,l+1,cdots,r}}}|, exttt{otherwise}end{cases}
]
这个东西 ( exttt{has been hacked by the Big Sample.})
一个可能的死亡原因：前缀后缀都要判断可能会引起一些错误。
处理方法：那么先处理前缀，后缀减一下再处理。
（这不是问题）
另一个可能的死亡原因：(min{min{P_{l,l+1,cdots,r}},min{S_{l,l+1,cdots,r}}}) 可能取到多处。
处理方法：。
（这也不是问题）
Algo. 0
W·violence·gy
Algo. 1
莫队，时间复杂度 (Theta(nsqrt{n}log_{2}n))。
Algo. 2
晓求不得。
Solution
Prob. 4
转化一下成最大子段和，化式子过程懒得写了。