改修放区间，答案放叶子的一种分治方法
考虑一个图是二分图当且仅当没有奇环，用扩展域并查集维护
类似线段树的方法，遍历到一个区间就下放完全包含这个区间的边，然后判断是不是二分图
回溯的时候删去影响，所以需要资瓷删除的并查集
用\(bitset\)维护每个位置的答案，最后合并到一起
过于毒瘤
考虑把每个点影响子树化为\(dfs\)序列上问题,然后线段树分治
对于题目，我们要求\(min\{(X-x_i)^2+c_i\}\),\(X\)每次给定
拆开\(=X^2-2Xx_i+x_i^2+c_i=k\)
变形一下\(2Xx_i+k=X^2+x_i^2+c_i\)
我们希望\(k\)最小，发现这是一个线性规划问题，对于每个决策点形如\((x_i,X^2+x_i^2+c_i)\)
但是对于每个\(X\)来说\(X^2\)固定不用加入决策，所以决策点变为\((x_i,x_i^2+c_i)\)
对于线段树的每个端点维护一个下凸包
如果我们大力平衡树维护复杂度\(O(nlog^2n)\)
观察发现可以按\(x_i\)离线插入，维护凸包变成均摊\(O(1)\)，复杂度\(O(blogn)\)
原文：https://www.cnblogs.com/knife-rose/p/12388274.html