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”作为结束。我们假设在一开始所有的道路都是堵塞的。 对30%测试数据，我们保证C小于等于1000，信息条数小于等于1000； 对100%测试数据，我们保证 C小于等于100000，信息条数小于等于100000。
Output
对于每个查询，输出一个“Y”或“N”。
将每条存在的边的按存在时间插入到线段树中，对线段dfs一次，用按秩合并、支持撤销的并查集维护连通性并回答询问。
此方法适用于离线的图连通性维护
时间复杂度O(clogclogn)
#include<cstdio> #include<algorithm> #include<vector> #include<set> inline int read(){ int x=0,c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x; } inline void exch(int&a,int&b){int c=a;a=b;b=c;} struct xy{int x,y;}; struct oper{int x,y,t;}; bool operator<(const oper&a,const oper&b){ if(a.x!=b.x)return a.x<b.x; return a.y<b.y; } std::set<oper>es; int oc=0; int n,m; std::vector<xy>ops[524288]; int qx[600005],qy[600005],f[100005]; char op[16]; inline void _ins(int w,int x,int y){ ops[w].push_back((xy){x,y}); } inline void ins(int l,int r,int x,int y){ for(l+=262142,r+=262144;l^r^1;l>>=1,r>>=1){ if(~l&1)_ins(l^1,x,y); if(r&1)_ins(r^1,x,y); } } inline void get(int&w,int&h){ h=0; while(w!=f[w])w=f[w],++h; } inline int get(int w){ while(w!=f[w])w=f[w]; return w; } int cs[600005],cp=0; void dfs(int w){ int cpx=cp; for(int i=0;i<ops[w].size();i++){ xy a=ops[w][i]; int h1,h2; get(a.x,h1);get(a.y,h2); if(a.x!=a.y){ if(h1<h2)f[a.x]=a.y,cs[cp++]=a.x; else f[a.y]=a.x,cs[cp++]=a.y; } } if(w<262144){ int lc=w<<1,rc=lc^1; dfs(lc); dfs(rc); }else{ w-=262143; if(qx[w])puts(get(qx[w])!=get(qy[w])?"N":"Y"); } while(cp>cpx)--cp,f[cs[cp]]=cs[cp]; } int main(){ n=read(); for(int i=1;i<=n+n+2;i++)f[i]=i; for(int i=2,x,y,r1,c1,r2,c2;;i++){ scanf("%s",op); if(op[0]=='E'){ m=i+3; break; } r1=read()-1;c1=read(); r2=read()-1;c2=read(); x=r1*n+c1;y=r2*n+c2; if(x>y)exch(x,y); if(op[0]=='A')qx[i]=x,qy[i]=y; if(op[0]=='O')es.insert((oper){x,y,i}); if(op[0]=='C'){ std::set<oper>::iterator w=es.find((oper){x,y,0}); ins((*w).t,i,(*w).x,(*w).y); es.erase(w); } } for(std::set<oper>::iterator w=es.begin();w!=es.end();++w)ins((*w).t,m+1,(*w).x,(*w).y); dfs(1); return 0; }