Codeforces Round #616 (Div. 1)

A

略

B

分成多段肯定不如分成两段 ([l,t],[t+1,r])，只需考虑 ([l,x]) 是否存在。满足以下条件之一有解：

1、(len=1)

2、(s_l e s_r)。构造：只需 (swap(s_l,s_r))

3、(s_l==s_r) 且字符种类数 (ge3)。证明：先构造 (ge3) 的解，找到 (x_1<x_2) 且 (s_{x1},s_{x2},s_l) 两两不同，然后交换 ((x_1,r),(x_2,l))，交换后 (t) 在区间 ([1,x_2-1]) 内 (s_{x2}) 的个数不同，在 ([x_2,n-1]) 内 (s_{x1}) 的个数不同，故不存在 (t)。然后证明一下 (<3) 时无解，若 (s_l=s_r=a)，则给出的串 (s'_l=s'_r=b)，考虑 (s,s') 中 (a) 数量的差值 (▲)。(t=1) 时 (▲=1)，(t=n-1) 时 (▲=-1)，而移动一位 (▲) 最多 (pm1)，所以必存在一个 (t) 使 (▲=0)，这样就挂了

C

每个 (x) 最多出现在两个集合 (A_x,B_x) 中。把每个集合 (p) 拆成两个节点 (p_0,p_1)，分别代表 (p) 在第一/二层，用并查集解决，记录每个集合中第一/二层点数。

若 (S_x=0)，则 (A_x,B_x) 需要选一个操作，合并 ((A_{x,0},B_{x,1}),(A_{x,1},B_{x,0}))，即 (A,B) 对立

若 (S_x=1)，(A_x,B_x) 状态相同，合并 ((A_{x,0},B_{x,0})(A_{x,1},B_{x,1}))

答案就是每个集合的 (min(第一层点数，第二层点数)) 之和除以二（重复两次）。但要注意 (A,B) 为 (0) 的情况

D

每 (frac{k}{2}) 个数分为一块，先块内去重，然后两两之间比较去重，次数 (frac{2n^2}{k}-n)。两两之间比较可以进一步优化，不必每次都清空重新加入，相当于在一张以 ((1,2)(1,3)...(2,3)(2,4)...) 为边的图上进行路径覆盖，可以划分为 (frac{n^2}{4}) 条路径，优化至 (frac{3n^2}{2k}-frac{n}{2})。还可以用类似方法优化至更优（略）

E

根据笛卡尔树的性质，把 (leq x) 的子序列拿出来。在笛卡尔树中，对于 (p)，极大区间 ([l,r] | max[l,r]=a_p, lleq pleq r)，([l,r]) 都在 (subtree(p)) 内。那么只要维护 (l_i,r_i)，(res=sum r_i-l_i+1)。求 (l) 和求 (r) 相似，以 (r) 为例。考虑把 (x-1) 变为 (x)，假设 (x) 在位置 (pos)，对于 (x) 左边的，(r_i=min(r_i,pos))；对于 (x)，(r_x=x)；对于右边的，(r_i=r_i+1)。

也就是要支持区间取 (min)，区间加，单点赋值，区间求和四种操作，用线段树beats搞。

F

这是一个凸包，所以如果选的向量定了，方案唯一。设第 (i) 个向量选了 (c_i) 个，合法的方案需要满足这些条件：(sum c_ix_i=sum c_iy_i=0, sumlimits_{x_i>0}c_ix_ileq m,sumlimits_{y_i>0}c_iy_ileq m)

进行二进制数位 (dp)，设四个方向的长度和为 (u,d,l,r)，(f[i][uu][dd][ll][rr][p][q]) 表示考虑了最后 (i) 位，后 (i) 位满足第一个等式，四个方向的进位为 (uu,dd,ll,rr)，(p,q) 表示 (u,l) 的后 (i) 位是否超过 (m) 后 (i) 位。(2^n) 枚举第 (i) 位状态转移。设 (L) 为 (x_i,y_i) 最大值，那么进位不会超过 (nL)，复杂度 (O(2^n(nL)^4log m))