题面
题解
考虑用并查集维护图的连通性，接着用线段树分治对每个修改进行分治。
具体来说，就是用一个时间轴表示图的状态，用线段树维护，对于一条边，我们判断如果他的存在时间正好在这个区间内，那就把它用并查集并起来。最后对于一个询问，直接用并查集找就好了。
但是因为有撤销操作，所以在并查集合并的时候，我们将需要合并的两个点放进栈中，最后栈序撤销，所以只能考虑按秩合并而不能路径压缩。
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::sort; using std::swap;
using std::unique; using std::lower_bound;
using std::map; using std::vector;
typedef long long ll;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 2e5 + 10;
int n, id[3][N], q_num, top, fa[N], siz[N], cnt;
map<int, int> G[N];
struct Edge { int u, v, beg, end; };
struct Node { int x, y; } q[N], stk[N << 2];
vector<Edge> e;
int find(int x) { while(fa[x] != x) x = fa[x]; return x; }
inline void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(siz[fx] > siz[fy]) swap(fx, fy);
fa[fx] = fy, siz[fy] += siz[fx], stk[++top] = (Node){fx, fy};
}
void doit (int l, int r, vector<Edge> E) {
vector<Edge> L, R;
int mid = (l + r) >> 1, tmp = top;
for(vector<Edge>::iterator it = E.begin(); it != E.end(); ++it)
if(it->beg <= l && it->end >= r) merge(it->u, it->v);
else {
if(it->beg <= mid) L.push_back(*it);
if(it->end > mid) R.push_back(*it);
}
if(l == r) puts(find(q[l].x) == find(q[l].y) ? "Y" : "N");
else doit(l, mid, L), doit(mid + 1, r, R);
while(top > tmp) {
int x = stk[top].x, y = stk[top--].y;
fa[x] = x, siz[y] -= siz[x];
}
}
int main () {
read(n);
for(int i = 1; i <= n; ++i)
id[1][i] = ++cnt, id[2][i] = ++cnt;
while(true) {
char s[10]; int r1, c1, r2, c2;
scanf("%s", s); if(s[0] == 'E') break;
read(r1), read(c1), read(r2), read(c2);
if(s[0] == 'O') {
G[id[r1][c1]][id[r2][c2]] = G[id[r2][c2]][id[r1][c1]] = e.size();
e.push_back((Edge){id[r1][c1], id[r2][c2], q_num + 1, -1});
} else if(s[0] == 'C') e[G[id[r1][c1]][id[r2][c2]]].end = q_num;
else if(s[0] == 'A') q[++q_num] = (Node){id[r1][c1], id[r2][c2]};
}
for(vector<Edge>::iterator it = e.begin(); it != e.end(); ++it)
if(it->end == -1) it->end = q_num;
for(int i = 1; i <= n + n; ++i) fa[i] = i, siz[i] = 1;
doit(1, q_num, e);
return 0;
}