JZTXT

Tricks

发布时间 2023-10-13 19:36:49作者: Aria_Math

图论

  • 拓扑排序中有形如"让某个点尽量早出队”的限制，可以建反图转化为“让某个点尽量晚出队”的形式。P1954，P3243。
  • \(k\) 个点的LCA为dfs序最大和最小的两点的LCA。
  • 根分别到 \(k\) 个点路径的并集可以差分为根到 \(k\) 个点的路径减去根到dfs序相邻两点的LCA的路径。

数据结构

  • 如果操作只涉及 and or 和 xor，可以考虑按位维护。
  • KD-Tree 如果涉及加点操作可以离线建树，每次激活新点即可。