DS

现在看其实还好。

最大值查询很烦，不能差分，分治一下就好了。

从前向后扫，维护序列颜色段，每个段有两个属性：颜色和权值。要查询的是颜色大于等于 $x$ 的权值和，再开一个树状数组维护这个就行了。

从左向右扫，求出每个位置的序列线性基，要求就是如果有 $k$ 个基底，则要求颜色数是 $2^k$，这样求出了 $\mathcal O(n\log n)$ 个区间。然后要查历史和状物。暴力做很不牛。

考虑对于一个 $k$，区间的左右端点都是单调的。所以预处理之后可以 $\mathcal O(1)$ 查询。

LCT，让虚实边对应轻重边。

修改只会修改不超过 $\mathcal O(\log n)$ 个点的重儿子。link 和 cut 的时候暴力跳检查一下是否需要改儿子就行了。对于换根，可以维护最大轻儿子减重儿子的大小，复杂度大概是对的（？）。

按照 $c$ 定长分块，不跨过边界的是好处理的。

对于跨过边界的，是一个三角形查询状物。

考虑在这个上面建线段树！分治！

矩形的答案可以通过两侧的三角形算出来，这样就可以合并了，总复杂度也是一个 $\log$。

首先所有数要先 $\bmod C$。对于 $(x+y)-C$ 的话，是取两个最大值。

对于 $x+y<C$ 的情况，考虑维护双向匹配的最大值。修改只会改 $\mathcal O(1)$ 个匹配。

倒着建 trie 可以做整体加一。一个点维护所有儿子形成的 trie，父亲特殊查询。然后做完了。

我是奶龙/dy。

一个环可以用 LCT 找出一段合法区间。一个连通块可以点减边，线段树维护。除了环以外度数不大于 $3$ 可以在 LCT 上维护度数最小值以及个数。上个历史和做完了。

ZR省选题