CF1263

$Div.2$

假设从小到大依次是 $a,b,c$ ,则先把 $a$ 用完,用的时候让 $b,c$ 尽可能接近,最后再加上剩下的 $b$ .

遇到一个已经出现过的串时,就把它改成一个在全局中都没有出现过的串.

可以改的有 $36$ 种串,而 $n\le 10$ ,所以每次一定都能选出.

整除分块裸题.记得把 $0$ 加上.

给 $26$ 种字符各自建一个虚拟节点,对于每个串,若它含有字符 $x$ ,就将它向 $x$ 的虚拟节点连边.

用并查集实现上面的过程,最后答案就是含有字符串节点的连通块数目.

左,右括号分别视作 $+1,-1$ ,用线段树维护每个前缀的权值,以及区间内前缀的最大值,最小值.

修改时是给一段前缀 $+1$ 或者 $-1$ .

询问时,若所有前缀最小值为 $0$ ,且最后一个前缀权值为 $0$ ,则合法.

此时询问的颜色种数,可以发现就是括号的最大深度,即所有前缀的最大值.

光标移到左边就不能移了,没写这个却 pp 了,喜提 FST .

考虑删掉一条边 $u\to v$ 时,子树 $v$ 里面的边就没有任何影响了.

为了让删去的边最多,就把子树 $v$ 里面的边也全部删掉.

从节点 $v$ 来看,可以删掉子树 $v$ 里面的所有边,以及它的父亲边 (如果有) ,这样会覆盖掉一段叶子 $[l,r]$ .

当每个叶子恰好被覆盖一次时,一定是最优的,而且容易发现这一定可以做到.

于是将每个节点看成一条线段 $[l,r]$ ,并且有一个收益 $c$ ,要求不重叠地覆盖 $[1,n]$ 时能获得的最大收益.

设 $f(i)$ 表示不重叠地覆盖 $[1,i]$ 时能获得的最大收益,每条线段 $[l,r]$ 只能去转移 $f(l-1)$ ,时间复杂度 $O(a+b)$ .