题目传送门：uoj46
题意简述：要求在序列上维护一个操作间支持结合律的区间操作，查询连续一段时间内的操作对单点的作用效果，\(n \leq 10^5,m \leq 6 \times 10^5\)。
刚开始看到这道题的时候想到树套树，然而需要用到的空间太大，时间复杂度无法承受，再一看有8s的时限，就试着强行对操作分块，看看能不能\(O(m \sqrt m)\)卡过去，不过极限数据下再怎么优化也要10s，卡不过去。
正解可以用二进制分组的思想，对操作序列维护一棵线段树，每个结点维护子树内的操作对序列每个元素的影响（相邻两个元素的影响相同合并成一个区间表示）。然而不同于普通线段树的是，该线段树仅在左右儿子都塞满操作的时候才更新父节点的信息，这样每个结点只会被更新一次。在更新父节点的时候，可以归并地把左右儿子的信息叠加，可以证明这样的修改复杂度均摊是\(O(m\log m)\)的。查询时可以把查询的时间区间分割到线段树的\(\log m\)个结点上，然后在在这些结点上二分查找待查询点的操作效果。总时间复杂度\(O(m\log^2m)\)，但实际上常数较小，能很快通过极限数据。
代码：