整体二分_杂项

整体二分

不详细说概念了，大概就是放在一起二分，从而压缩掉一些操作。

常见的写法就是 void sol(L,R,vec) 表示 vec 里面的点二分到 L,R。

当然如果具有某种决策单调性我们可以把 vec 换成 l,r。

大多数时候需要撤销，即判断完 mid 之后撤销 $[l,mid]$ 的事件，然后递归左边，然后再加上再递归右边。

非递归式整体二分

更接近本质的叙述。

每个询问维护一个 $[L,R]$，进行充分多次的整体值域扫描，我们会遇到 $\mathcal O(n)$ 个事件，即遇到一个 $\rm mid$ 就判断，遇到一个修改事件就修改，总复杂度 $\mathcal O(n\log V)$。

好处是避免了撤销，更清晰直观。