图论
- 拓扑排序中有形如"让某个点尽量早出队”的限制,可以建反图转化为“让某个点尽量晚出队”的形式。P1954,P3243。
- \(k\) 个点的LCA为dfs序最大和最小的两点的LCA。
- 根分别到 \(k\) 个点路径的并集可以差分为根到 \(k\) 个点的路径减去根到dfs序相邻两点的LCA的路径。
数据结构
- 如果操作只涉及
and
or
和xor
,可以考虑按位维护。 - KD-Tree 如果涉及加点操作可以离线建树,每次激活新点即可。
and
or
和 xor
,可以考虑按位维护。