题解

早就想写线段树分治的题了。

对于每条边，它存在于一段时间

我们按时间来搞

我们可把一条边看做一条线段

我们可以模拟线段树操作，不断分治下去

把覆盖\(l-r\)这段时间的线段筛选出来,用并查集维护联通性，回溯时撤销操作

注意不能使用路径压缩（不能破坏树的结构，方便撤销操作）

Code

#include
    
     #define LL long long#define RG registerusing namespace std;inline int gi() {    int f = 1, s = 0;    char c = getchar();    while (c != '-' && (c < '0' || c > '9')) c = getchar();    if (c == '-') f = -1, c = getchar();    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();    return f == 1 ? s : -s;}const int N = 10010, M = 200010;struct question {    int time, u, v;}q[M];int ql, w;struct bian {    int u, v, s, e;};vector
     
       g;map
      
       
        , int> Mp;int siz[N], fa[N];inline int find(int x) {    return x == fa[x] ? x : find(fa[x]);}pair
        
          stk[M];int top;void link(int x, int y) {//按秩合并    x = find(x); y = find(y);    if (x == y) {        stk[++top] = make_pair(0, 0);        return ;    }    if (siz[x] < siz[y]) swap(x, y);    stk[++top] = make_pair(x, y);//y接在x上    fa[y] = x;    siz[x] += siz[y];    return ;}void clear() {//撤销操作    int x = stk[top].first, y = stk[top--].second;    if (!x && !y) return ;    fa[y] = y;    siz[x] -= siz[y];    return ;}void divide(int l, int r, vector
         
           E) { vector
          
            L, R; int tmp = top, mid = (l + r) >> 1; for (int i = 0; i < (int)E.size(); i++) { if (E[i].s <= l && E[i].e >= r) link(E[i].u, E[i].v); else { if (E[i].s <= mid) L.push_back(E[i]); if (E[i].e > mid) R.push_back(E[i]); } } if (l == r) { while (q[w].time == l && w <= ql) { if (find(q[w].u) == find(q[w].v)) printf("Yes\n"); else printf("No\n"); w++; } if (w > ql) exit(0); return ; } else divide(l, mid, L), divide(mid+1, r, R); while (top > tmp) clear(); return ;}int main() { int n = gi(), m = gi(), x, y; char s[10]; for (int i = 1; i <= m; i++) { cin >> s >> x >> y; if (x > y) swap(x, y); if (s[0] == 'C') { if (Mp.find(make_pair(x, y)) == Mp.end()) g.push_back((bian){x, y, i, m}), Mp[make_pair(x, y)] = g.size()-1; } else if (s[0] == 'D') { g[Mp[make_pair(x, y)]].e = i-1; Mp.erase(Mp.find(make_pair(x, y))); } else q[++ql] = (question) {i, x, y}; } /*for (int i = 0; i < g.size(); i++) printf("%d %d %d %d\n", g[i].u, g[i].v, g[i].s, g[i].e);*/ w = 1; for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1; divide(1, m, g); return 0;}