A. 取(a=r+1),因此只需判断(l)和(dfrac{r+1}2)的大小关系.
B. 如果有(k)对连续两个相同的位置,那么答案为(lceildfrac k2
ceil).
C. 从小到大排序,(f(i,j))表示考虑到第(i)个数,当前(T)为(j)的最优解,(f(i,j)=|t_i-j|+min_{k<j}f(i-1,k)).(j)的取值范围不会超过(2n).复杂度为(O(n^3))或(O(n^2))均可.
D. 模拟.
E. 考虑不带限制的做法,令(a'_i=a_i-i),即求({a'_i})的最长不下降子序列.带上限制后分段求最长不下降子序列即可.复杂度(O(nlog n)).
F. 从大到小排序,如果存在(i>2)使得(2a_i>a_1),则不存在合法的序列.
记(dp_i)为只考虑区间([1,i]),并且(a_i)在序列第一位的方案数.在序列末尾增加(a_{n+1}=0),则答案为(dp_{n+1}).
考虑(dp_i)到(dp_j)的转移:首先需要满足(2a_jleq a_i),再考虑区间((i,j))中数的位置方案数.
如果其中有(m)个值大于(dfrac{a_i}2,p)个值小于等于(dfrac{a_i}2),那么这(m)个值必须放在区间([1,i-1])的数的后面,而这(p)个值可以放在(a_i)后面.
因此考虑组合数,(dp_j+=dp_idfrac{(i+m-2)!}{(i-2)!}dfrac{(i+m+p-1)!}{(i+m-1)!}).复杂度(O(n^2)).
G. 构建AC自动机,考虑fail树,每个节点可能对应多个名字(名字可能相同),每次修改相当于修改某个节点上的某个值.对每个询问串,当遍历到每个节点的时候,都需要考虑从该节点到根的最大值.可以使用树链剖分和线段树维护答案.记(t=sum|s_i|,k=sum|q|),复杂度为(O(t+klog^2t)).