Nityacke

线段树 一般线段树维护的东西是什么？设其维护的信息的半群 \((A,+)\)，维护标记的半群 \((T,\times)\) 和一种运算 \(*\mapsto A*T\to A\)。 要求 \((b+c)*a=b*a+c*a\)。 一般而言，矩阵是满足这东西的最一般东西，所以线段树一定可以用矩阵搞。 ......

我们有对序列分块的需求。所以我们有对树分块的需求。 有些出题人喜欢把序列问题放到树上，从而让选手强行写树链剖分。 但是我们想让大家知道，搬到仙人掌上也是可以的。 先给出一些信息： 一个树簇 (cluster) 是树上的一个连通子图，有至多两个点和全树的其他位置连接。 这两个节点被称为界点，可以证明， ......

P2801 教主的魔法 区间加区间查询一个数排名。 对于每个块，维护其有序序列。修改时散块暴力重构，整块打tag。 查询是简单的。时间复杂度 \(O(n\log B+\dfrac{qn}{B}\log B+qB)\)。 \(B=\sqrt{n\log n}\)时复杂度为\(O(n\sqrt{n}\l ......