Description
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可
以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个
城市和3C-2条道路。 小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，
直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度
发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通
部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：
Close r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了；Open r1 c1 r2 c2：相邻的两座城
市(r1,c1)和(r2,c2)之间的道路被疏通了；Ask r1 c1 r2 c2：询问城市(r1,c1)和(r2,c2)是否连通。如果存在一
条路径使得这两条城市连通，则返回Y，否则返回N；
Input
第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为
结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000，信息条数小于等于100000。
Output
对于每个查询，输出一个“Y”或“N”。
题目分析
这里提供一种更加一般的模型，即离线动态图连通性。
大体的思路是：把所有操作都离线之后，对询问分治，将每个询问看做线段树的一个节点（因为询问天然有序），并且记录当前剩余操作（可以是在过程里带vector）。那么这样在处理到每个叶子节点的时候，就已经把有关的操作都执行了。最后离开当前节点时，按栈序撤销并查集操作。
这个方法的时间复杂度是$O(m \log m \log n)$（$\log n$是可撤销并查集的复杂度）。其优化的本质在于，让一段共用边的操作同时处理。
那么这里有一个很具有启发性的思路：对于一类询问$m$次，每次询问基于若干个元素的问题，可以通过离线分治的方式减少它们的冗余操作，将复杂度将为$O(m \log m \log n)$。当然最大的缺陷在于必须离线（而且过程里挂vector是不是太占空间了？）
#include<bits/stdc++.h>
const int maxn = ; struct Edge
{
int u,v,s,t;
Edge(int a=, int b=, int c=, int d=):u(a),v(b),s(c),t(d) {}
};
int n,qNum,top;
int mp[][maxn],fat[maxn],size[maxn];
typedef std::vector<Edge> vec;
vec opt;
std::map<int, int> tag[maxn];
std::pair<int, int> qr[maxn],stk[maxn<<];
char str[]; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
int find(int x)
{
while (x!=fat[x]) x = fat[x];
return x;
}
void merge(int x, int y)
{
int fx = find(x), fy = find(y);
if (size[fx] > size[fy]) std::swap(fx, fy);
stk[++top] = std::make_pair(fx, fy);
fat[fx] = fy, size[fy] += size[fx];
}
void cancel()
{
int x = stk[top].first, y = stk[top].second;
fat[x] = x, size[y] -= size[x];
}
void solve(int l, int r, vec opt)
{
vec L,R;
int mid = (l+r)>>, tmp = top;
for (int i=, mx=opt.size(); i<mx; i++)
{
int s = opt[i].s, t = opt[i].t;
if (s <= l&&r <= t) merge(opt[i].u, opt[i].v);
else{
if (s <= mid) L.push_back(opt[i]);
if (t > mid) R.push_back(opt[i]);
}
}
if (l==r) puts(find(qr[l].first)==find(qr[l].second)?"Y":"N");
else solve(l, mid, L), solve(mid+, r, R);
while (tmp!=top) cancel(), --top;
}
int main()
{
n = read();
for (int i=, cnt=; i<=n; i++)
mp[][i] = ++cnt, mp[][i] = ++cnt;
for (int idx,idy; ;)
{
scanf("%s",str);
if (str[]=='E') break;
idx = mp[read()][read()], idy = mp[read()][read()];
if (str[]=='O'){
opt.push_back(Edge(idx, idy, qNum+, -));
tag[idx][idy] = tag[idy][idx] = opt.size()-;
}
if (str[]=='C') opt[tag[idx][idy]].t = qNum;
if (str[]=='A') qr[++qNum] = std::make_pair(idx, idy);
}
for (int i=, mx=opt.size(); i<mx; i++)
if (opt[i].t==-) opt[i].t = qNum;
for (int i=; i<=(n<<); i++) fat[i] = i, size[i] = ;
solve(, qNum, opt);
return ;
}
END