【CDQ分治】HDU1520-Tunnel Warfare
离线分治大法好啊！！
题意
区间有n<=50000个点，m<=50000次操作。一开始所有点都是相连的。有三种操作。1 断开某个点。2 恢复上次断开的点。 3 查询某个点属于的线段的长度。
这个题本来是在集训队的线段树作业里。今天学了CDQ分治突发奇想好像可以做…..然后就做了。虽然当时我也是用set做的
思路源于set的在线算法。
set本质平衡树。每次读到一次断开操作，在平衡树中加入这个节点。查询的时候在平衡树里查找第一个比它大的和第一个比它小的数字。其差值就是答案。
恢复操作需要用一个栈存起来。然后从平衡树里删除这个值。总复杂度NlogN,其中N指的操作总数
这里有个坑点。断开操作可能会有重复。比如先断开 3 再断开 4 然后再断开 3 。虽然对查询操作没有影响，但是恢复操作的时候第一个恢复的是 3 这个点…..我因为这个WA了好久
但是虽然STL里面有set，但如果不能用STL或者不会写平衡树怎么办呢。
重点来了：CDQ分治
CDQ分治是一种基于时间分治的离线算法。其核心思想就是基于前面的操作会对后面的查询造成影响。所以可以把查询离线，根据时间顺序，计算修改操作对之后每个查询的影响。
然而这题有点特别就是有撤销操作。每次修改对后面询问的影响都可能被撤销。如果单单按照操作顺序作为时间分治，还需要用到可持久化的数据结构。
但是换个思路。既然每个操作有撤销，那么就考虑每个操作的”存活时间”。
每个操作在撤销之前对其间的询问都会造成影响。考虑每个操作的存活时间，把询问根据存活时间分治。
比如”DDDRQDQ”，其中第三个D的存活时间为0，因为它没有对任何询问造成影响。第一、二个询问的存活时间都为2，考虑其出生时间，记为[1,2]，最后一个D则是[2,2]。
接下来把相应的询问安排到相应的区间。有点类似于线段树的感觉。在每个断开操作造成影响的询问操作的区间加上它。
在每个区间分治的时候把修改和询问一起排序。因为CDQ分治的正确性，修改一定会对只后的询问造成影响，所以可以把坐标排序。然后从左往右，从右往左扫一次。依次找出每个询问最近的修改就可以啦。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 233;
struct dt{
int x,l,r;
}a[maxn];
int n,m,q[maxn],ansl[maxn],ansr[maxn],vis[maxn];
pair<int,int> b[maxn];
vector<int> g[maxn * 4];
void cg(int k, int l, int r,int x,int y,int id)
{
if(x > y) return;
if(l > r || l > y ||