简单数据结构
例题
CF103D
(ygeq sqrt m)时暴力做
(y< sqrt m)时暴力与处理
bzoj2054
倒序处理，只有最后一个覆盖操作对这个位置有影响
并查集维护每个位置的下一个未覆盖的位置
CF480E
倒序操作，答案显然是不降的
枚举一个当前的答案(ans)，判断每次是否可以(+1)
(check(ans+1))的话只需要考虑新增的正方形，即有一列是确定的，维护一下每个格子最远可以向左/右多少个格子，用一个(sliding windows)和单调队列进行check即可
ZJOI2016 旅行者
考虑分治
假设两个点的路径一定会经过中间的线（假设纵向切割）。枚举中间的线上的某一点并强制路径经过它，使用Dijkstra求出这个点到路径两端的的距离。两个点在同一侧的时候还需要继续分治下去。
时间：(T(n,m)=O(n^2mlognm)+2T(n,frac{m}{2}))
另(S=nm)，每次取较长的边分治是更优的，则(T(S)=O(Ssqrt S)+2T(frac{S}{2})=O(Ssqrt SlogS))
进阶数据结构
分治
基础
平面最近点对
分治求左半边和右半边的最小距离(H)，只需要考虑分界线两边距离为(H)的矩形内的点，每次check时不需要枚举很多年的点对（大致只需检查(6)个左右，考虑一个长(2H)宽(H)的矩阵，这里面最多放入(6)个点使得两两之间距离至少为(H)）
One Problem
类似上一题的分治
树分治(点分治)
重心：所有子树的(size)均(leq frac{n}{2})
bzoj1468(solved)
模板题
bzoj2599(solved)
同上，注意由于维护的是最小值无法通过容斥求得
One Problem
咕
cdq分治（按时间分治）
时间在前的操作才会对时间在后面的操作产生影响
三维偏序
记(z)为时间维度，按照(z)排序。分治后只需考虑左半边对右半边的贡献，直接树状数组
(T(n)=2T(frac{n}{2})+O(nlogn))即(O(nlog^2n))
bzoj2683
对时间维度建立分治结构，只考虑前面的加对后面的询问的影响，接下来同上
bzoj2716
(ans=|x_i-x_j|+|y_i-y_j|)
暴力拆绝对值，跑四遍cdq
假设(x_i>x_j,y_i>y_j)，则(ans=(x_i+y_i)-(x_j+y_j))，每次询问(max(x_j+y_j))即可
整体二分
POJ2104(q<=2*10^5)
模板题，略
LOJ2169
同上
线段树分治
bzoj4025(solved)
在插入边的同时判断是否为二分图：带权并查集，维护每个点到它所在的子树的根的距离，在同一棵树加边时判断是否会形成奇环
对于每一条边的存在时间([L,R])，把它放到线段树上拆成log段，按照遍历线段树的方式进行修改，在所有的叶子节点处处理询问。这样的话需要维护一个支持回退的并查集，如果路径压缩的话时间复杂度会退化成(O(n))，故只能按秩合并。总时间复杂度(O(nlog^2n))
例题
HNOI2016 网络
重链剖分：往上跳的轻边条数是(O(logn))条(记(u)的重儿子为(v),则(siz_u>2siz_v)，故跳轻边时子树大小至少除以2)
维护删除：维护两个堆(P,Q)，其中(P)处理插入，(Q)处理删除，每次询问时找到(P.top())与(Q.top())，相同则同时弹出（使用线段树分治可以避免使用堆，但是时间复杂度均为(O(nlog^3n))
二分(mid)，检查所有(geq mid)的路径的交是否包括(u)，单个询问会有3个(log)的时间(线段树分治+二分+倍增LCA)
整体二分：插入删除路径使用树上差分，强制在线的话可以转化成单点修改，区间（子树）查询，BIT维护。分治时将插入删除分至两边：
直接二分：询问是否有(geq mid)且不经过(u)的路径。线段树([l,r])维护(forall win[l,r])路径的交
ARC093F
假设(1)在第1位，记(G_i=[p_{2^{k-1}+1},p_{2^k}])，则(min(G_i) otin A)
容斥，枚举(Sin[n])，有(forall iin S,min(G_i)in A)
(f[i][S]):在(a_m...a_i)中，(S)中(G)的最小值在其中的方案数