线段树合并 学习笔记

线段树分治

P5787

考虑怎么判断二分图。先考虑弱化的版本。

• 不考虑删边加边，则可以直接黑白染色。
• 考虑只加边，不删边，分类讨论：
  • 注意到对于同一个连通块，一共只有两种染色方式。
  • 加的边在两个连通块之间，一定是 Yes，并确定了两个连通块的染色方案。
  • 加的边在连通块内，直接判断。
  • 这样单次复杂度就都是 \(O(1)\) 的了。

但是删边怎么办呢？

如果插入是好插入的，删除是难删除的，这样的题目就可以考虑线段树分治。