CF1129

link ### A 随便搞搞就做完了。

B

考虑一个序列：\(n\)个\(0\)，然后\(1\)个\(-1\)，然后\(m\)个数\(a_1\dots a_m\)，其中\(a_1\ge 1,a_i\ge 0\)，设\(s=\sum a_i\) 差就是\((s-1)(n+1+m)-ms=(n+1)s-n-1-m=k\)

所以\(s=\frac{k+m+n+1}{n+1}\)。

枚举\(n,m\)，判断下是否合法（\(s\)是整数且\(s\le 10^6m\)。

C

设\(f(l,r)\)表示得到S[l:r]的方案数。

然后用trie判断一下每个后缀是否出现过。

D

设\(f_i\)表示前\(i\)个数可行的划分方案数。

设\(s_j\)表示\((j,i]\)区间内只出现了一次的元素个数。

则\(f_i=\sum_j [s_j\le k]f_j\)

设\(p_i\)表示\(a_i\)上一次出现的位置。

当i+=1的时候，\(s_{p_i...i-1}\)+=1,\(s_{p_{p_i}...p_i-1}\)-=1。

然后分块维护一下就好了。

E

记一次询问为\((S,T,v)\)。

首先把这个树以\(1\)为根。\(d_i=(\{1\},\{2,3,...,i-1,i+1,...,n\} a,i)\)表示\(i\)子树大小-1。

接着把点按照\(d\)升序排序为\(v_1,v_2...v_{n-1}\)

记录\(X\)集合为还没有找到父亲的点集合。

初始\(X=\{v_1\}\)

按顺序从\(v_2\)开始考虑每个点：

询问\((\{1\},X,v_i)\)得到\(v_i\)的儿子个数\(k\)。

然后\(k\)次，每次把点随便排列，二分。-------------------------