题目传送门

离线分治大法好啊！！

题意

区间有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 || r < x) return;
    if(x <= l && y >= r)
    {
        g[k].push_back(id);
        return;
    }
    if(l == r) return;
    int mid = (l + r) >> 1;
    cg(k*2,l,mid,x,y,id); cg(k*2+1,mid+1,r,x,y,id);
}
void cdq(int k, int l, int r)
{
    if(l > r) return;
    int t = 0;
    for(auto &i : g[k])
    {
        b[++t] = {a[i].x, 0};
    }
    for(int i = l; i <= r; i++) b[++t] = {q[i],i};
    sort(b + 1, b + 1 + t);
    int tmp = -1;
    for(int i = 1; i <= t; i++) 
    {
        if(b[i].second == 0) tmp = b[i].first;
        if(b[i].second != 0 && tmp != -1) ansl[b[i].second] = max(ansl[b[i].second], tmp); 
    }
    tmp = -1;
    for(int i = t; i >= 1; i--)
    {
        if(b[i].second == 0) tmp = b[i].first;
        if(b[i].second != 0 && tmp != -1) ansr[b[i].second] = min(ansr[b[i].second], tmp);
    }
    if(l == r) return;
    int mid = (l + r) >> 1;
    cdq(k * 2, l, mid);
    cdq(k * 2 + 1, mid + 1, r);
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
    for(int i = 1; i <= maxn * 4 - 233; i++) g[i].clear();
    memset(vis,0,sizeof vis);
    char opr[5];
    int cnt = 0, tot = 0;
    stack<int> stk;
    for(int i = 1; i <= m; i++)
    {
        scanf("%s",opr);
        if(opr[0] == 'D')
        {
            int k;
            scanf("%d",&k);
            if(vis[k] == 0) a[++tot] = {k, cnt + 1, -1},vis[k] = tot;
            stk.push(k); 
        }
        else if(opr[0] == 'R')
        {
            int re = stk.top();stk.pop();
            a[vis[re]].r = cnt;
            vis[re] = 0;
        }
        else
        {
            int k;
            scanf("%d",&k);
            q[++cnt] = k;
        }
    }
    for(int i = 1; i <= cnt; i++) ansr[i] = n + 1;
    memset(ansl,0,sizeof ansl);
    for(int i = 1; i <= tot; i++) if(a[i].r == -1) a[i].r = cnt;
    for(int i = 1; i <= tot; i++) cg(1, 1, cnt, a[i].l, a[i].r, i);
    if(tot) cdq(1,1,cnt);
    for(int i = 1; i <= cnt; i++)
    {
        if(ansr[i] == q[i] || ansl[i] == q[i]) printf("0\n");
        else printf("%d\n",ansr[i] - ansl[i] - 1);
    }
    } 
}

由于本题离线查询是线性，但有个排序操作，所以是O(NlogN)的，CDQ分治部分总复杂度O(Nlog^{2}N)，其中N表示查询操作的个数。