知识点：线段树分治，可撤销并查集

原题面：Loj

扯

zr sb出题人出裸题 = =
然后就来抄了份板子（

题意简述

给定 \(n\) 个节点，初始时图中没有边。有 \(m\) 次操作：

1. 加入一条不存在的边。
2. 删除一条存在的边。
3. 查询给定点对是否连通。

\(1\le n\le 5000\)，\(1\le m\le 5\times 10^5\)。

分析题意

只有加边操作就是并查集板子。
但发现并查集并不能很好地处理撤销操作。

发现该题满足「线段树分治」的模型：

1. 给定一些仅在 给定时间范围 内有效的操作。
2. 询问某个时间点所有操作的贡献。

考虑离线操作，对时间轴建立线段树，将每个操作转化为线段树上的区间标记操作。
查询时遍历整棵线段树，到达每个节点时执行相应的操作，到达叶节点统计贡献，回溯时撤销操作的影响

于是考虑线段树分治，对时间轴建立线段树。
用 vector 维护时间区间内存在的边集。

查询时从根节点出发开始遍历，递归处理时将当前节点存在的边进行合并。
深入到叶节点后看该时刻有无查询操作，若有则回答询问。

回溯时，发现并查集并不支持删除操作。
考虑可撤销并查集，使用一个栈记录下对并查集的操作，将父子关系再改回去。
则不可使用路径压缩，否则操作次数爆炸，为保证复杂度，应进行按秩合并。

总复杂度 \(O(m\log m\log n)\)。

代码实现

//知识点：线段树分治，可撤销并查集
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#define pr std::pair
#define mp std::make_pair
#define LL long long
const int kMaxn = 5e4 + 10;
const int kMaxm = 5e5 + 10;
//=============================================================
struct Operation {
  int type, u, v;
} opt[kMaxm << 1];
struct Stack {
  int u, v, fa, size;
} st[kMaxm];
int n, m, k, top, fa[kMaxn], size[kMaxn];
std::map <pr <int, int>, int> tim;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == \'-\') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ \'0\');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
int Find(int x_) {
  while (x_ != fa[x_]) x_ = fa[x_];
  return x_;
}
void Union(int u_, int v_) {
  int fu = Find(u_), fv = Find(v_);
  if (size[fu] > size[fv]) std :: swap(fu, fv);
  st[++ top] = (Stack) {fu, fv, fa[fu], size[fu]};
  if (fu != fv) {
    fa[fu] = fv;
    size[fv] += size[fu];
    size[fu] = 0;
  }
}
void Restore() {
  Stack now = st[top];
  if (now.u != now.v) {
    fa[now.u] = now.fa;
    size[now.v] -= now.size;
    size[now.u] = now.size;
  }
  top --;
}
namespace Seg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  std::vector <int> t[kMaxm << 2];
  void Modify(int now_, int L_, int R_, int l_, int r_, int val_) {
    if (l_ <= L_ && R_ <= r_) {
      t[now_].push_back(val_);
      return ;
    }
    if (l_ <= mid) Modify(ls, L_, mid, l_, r_, val_);
    if (r_ > mid) Modify(rs, mid + 1, R_, l_, r_, val_);
  }
  void Solve(int now_, int L_, int R_) {
    for (int i = 0, lim = t[now_].size(); i < lim; ++ i) {
      Operation nowo = opt[t[now_][i]];
      Union(nowo.u, nowo.v);
    }
    if (L_ == R_) {
      if (opt[L_].type == 2) {
        int u = opt[L_].u, v = opt[L_].v;
        printf("%c\n", Find(u) == Find(v) ? \'Y\' : \'N\');
      }
      for (int i = 0, lim = t[now_].size(); i < lim; ++ i) {
        Restore();
      }
      return ;
    }
    Solve(ls, L_, mid);
    Solve(rs, mid + 1, R_);
    for (int i = 0, lim = t[now_].size(); i < lim; ++ i) {
      Restore();
    }
  }
}
//=============================================================
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; ++ i) {
    int nowo = read(), u = read(), v = read();
    opt[i] = (Operation) {nowo, u, v};
    if (u > v) std::swap(u, v);
    if (nowo == 0) {
      tim[mp(u, v)] = i;
    } else if (nowo == 1) {
      Seg::Modify(1, 1, m, tim[mp(u, v)], i - 1, i);
      tim[mp(u, v)] = 0;
    } 
  }

  for (std::map <pr<int, int>, int>::iterator it = tim.begin(); it != tim.end(); ++ it) {
    if (it->second) {
      Seg::Modify(1, 1, m, it->second, m, it->second);
    }
  }
  for (int i = 1; i <= n; ++ i) {
    fa[i] = i;
    size[i] = 1;
  }
  Seg::Solve(1, 1, m);
  return 0;
}