线段树分治+并查集

线段树本身就是分治结构，碰见这种带删除修改的题目是再合适不过的，我们对于每段修改区间在线段树上打标记，每次路过就进行修改，叶子结点表及答案，先把所有修改在线段树上标记，然后dfs就行了

但是并查集怎么恢复呢？我们只要维护一个栈，保存某次操作之前这两个点的信息，dfs本身就是利用栈来操作，那么每次回溯就用栈的信息恢复之前的样子就行了

#include
      
       using namespace std;const int N = 100010;int c, tot, cnt, top, ask;int fa[N], l[N], r[N], d[N], mark[N];bool ans[N];struct dsu {    int u, v, fa, du, dv;    dsu(int u = 0, int v = 0, int fa = 0, int du = 0, int dv = 0) : u(u), v(v), fa(fa), du(du), dv(dv) {}} st[N];pair
       
         operation[N];map
        
         
          , int> mp;vector
          
           
             > tree[N << 2], q[N << 2];char opt[10];inline int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f;}int find(int x){ return x == fa[x] ? x : find(fa[x]);}int id(int x, int y){ return (x - 1) * c + y;}void unite(pair
            
              o){ int x = find(o.first), y = find(o.second); if(d[x] > d[y]) swap(x, y); st[++top] = dsu(x, y, fa[x], d[x], d[y]); if(x != y) { d[y] += d[x]; fa[x] = y; }}void del(int now){ while(top != now) { dsu x = st[top]; fa[x.u] = x.fa; d[x.u] = x.du; d[x.v] = x.dv; --top; }}void update(int l, int r, int x, int a, int b, pair
             
               o){ if(l > b || r < a) return; if(l >= a && r <= b) { tree[x].push_back(o); return; } int mid = (l + r) >> 1; update(l, mid, x << 1, a, b, o); update(mid + 1, r, x << 1 | 1, a, b, o);}void dfs(int l, int r, int x){ int now = top; for(int i = 0; i < tree[x].size(); ++i) unite(tree[x][i]); if(l == r) { for(int i = 0; i < q[l].size(); ++i) { pair
              
                o = q[l][i]; if(find(o.first) == find(o.second)) puts("Y"); else puts("N"); } del(now); return; } int mid = (l + r) >> 1; dfs(l, mid, x << 1); dfs(mid + 1, r, x << 1 | 1); del(now); }int main(){// freopen("bzoj_1018.in", "r", stdin);// freopen("bzoj_1018.out", "w", stdout); memset(l, 0x3f3f, sizeof(l)); c = read(); for(int i = 1; i <= 2 * c; ++i) { fa[i] = i; d[i] = 1; } while(scanf("%s", opt)) { if(opt[0] == 'E') break; ++tot; int r1 = read(), c1 = read(), r2 = read(), c2 = read(), u = id(r1, c1), v = id(r2, c2); if(u > v) swap(u, v); if(opt[0] == 'O') { if(mp.find(make_pair(u, v)) != mp.end()) continue; l[++cnt] = tot; operation[cnt] = make_pair(u, v); mp[make_pair(u, v)] = cnt; } if(opt[0] == 'C') { if(mp.find(make_pair(u, v)) == mp.end()) continue; r[mp[make_pair(u, v)]] = tot - 1; mp.erase(make_pair(u, v)); } if(opt[0] == 'A') q[tot].push_back(make_pair(u, v)); } for(int i = 1; i <= cnt; ++i) { if(!r[i]) r[i] = tot; update(1, tot, 1, l[i], r[i], operation[i]); } dfs(1, tot, 1); for(int i = 1; i <= ask; ++i) if(ans[i]) puts("Y"); else puts("N");// fclose(stdin);// fclose(stdout); return 0;}