2024.9.[23, 24]训练记录

23 上午

whk。
辅助角公式。
诱导公式。

23 下午

莫队：原序列分块。
询问排序：第一关键字为左端点所在块的编号，第二关键字为右端点编号。

回滚莫队：适用于增加或删除操作其中一个复杂度较大，但另一个较小的情况。可以做到只使用一种操作。

排序后按照左端点的块编号一块一块做。
排完序后，同一块内的询问的右端点就是有单调性的。
如果左右端点都在这一块内的话，长度不超过 \(O(\sqrt {n})\)，可以暴力做。（这里要分析一下复杂度）
如果是单调删，应该也可以不暴力做，归到一块。
在每次移完这一个询问的指针后，下一次询问，右端点可以在此基础上继续移。

此时。将左指针撤销到这一块的边上。
具体哪一边看是单调删还是单调插。相当于左指针每次从块的边上 删/插 到询问的左端点。
撤销操作的复杂度也需要单独分析。

省流：块内询问，右端点单调移，左端点每次撤销到边上再移。

其实就是把 插入/删除 操作变成了 插入/撤销 和 删除/撤销。只要 撤销 的复杂度和 插入/删除 其中一个复杂度都可接受。就可以回滚。