记录编号	375584	评测结果	WWAWWAAAAA
题目名称	[SHOI 2008]堵塞的交通traffic	最终得分	60
用户昵称	Vergil	是否通过	未通过
代码语言	C++	运行时间	0.534 s
提交时间	2017-02-25 15:24:19	内存使用	7.15 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define maxn 200005
struct query
{
	int x,y;
}q[maxn],st[maxn];
struct edge
{
	int u,v,st,en;
};
int id[3][maxn],n,tot,m,ans[maxn],siz[maxn],top,father[maxn];
map<pair<int,int>,int>  cnt,last;
vector<edge> e;
char s[10];

inline int read(void) 
{
	int ch=getchar();
	int x=0;
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') 
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

int getfather(int x) 
{
	if (x==father[x]) return x;
	return getfather(father[x]);
}

void restore(int x)
{
	while (top!=x) 
	{
		int fx=st[top].x;
		int fy=st[top].y;
		top--;
		father[fy]=fy;
		siz[fx]-=siz[fy];
	}
}

void solve(int l,int r,vector<edge> &e) 
{
	int size=e.size();
	int cur=top;
	int mid=(l+r)>>1;
	vector<edge> e1,e2;
	for (int i=0;i<size;i++) 
	{
		edge w=e[i];
		if (e[i].st==l&&e[i].en==r) 
		{
			int fx=getfather(e[i].u);
			int fy=getfather(e[i].v);
			if (fx==fy) continue;
			if (siz[fx]<siz[fy]) swap(fx,fy);
			father[fy]=fx;
			siz[fx]+=siz[fy];
			st[++top]=(query){fx,fy};
			continue;
		}
		if (w.en<=mid) e1.push_back(w);
		else if (w.st>mid) e2.push_back(w);
		else 
		{
			e1.push_back((edge){w.u,w.v,w.st,mid});
			e2.push_back((edge){w.u,w.v,mid+1,w.en});
		}
	}
	if (l==r) 
	{
		if (q[l].x) 
		{
			int fx=getfather(q[l].x);
			int fy=getfather(q[l].y);
			if (fx==fy&&q[l].x!=q[l].y) ans[l]=1;
		}
		restore(cur);
		return;
	}
	solve(l,mid,e1);
	solve(mid+1,r,e2);
	restore(cur);
}

int main()
{
	freopen("bzoj_1018.in","r",stdin);
	freopen("bzoj_1018.out","w",stdout);
	n=read();
	for (int i=1;i<=2;i++)
		for (int j=1;j<=n;j++) id[i][j]=++tot;
	n=tot;
	while (1) 
	{
		int r1,r2,c1,c2;
		scanf("%s",s);
		if (s[0]=='E') break;
		m++;
		r1=read();c1=read();r2=read();c2=read();
		int x=id[r1][c1],y=id[r2][c2];
		if (x>y) swap(x,y);
		if (s[0]=='O')
			if (++cnt[make_pair(x,y)]==1) last[make_pair(x,y)]=m;
		if (s[0]=='C') 
		{
			if (cnt[make_pair(x,y)]==0) continue;
			if (--cnt[make_pair(x,y)]==0)
				e.push_back((edge){x,y,last[make_pair(x,y)],m});
		}
		if (s[0]=='A') 	q[m]=(query){x,y};
	}
	map<pair<int,int>,int>::iterator it;
	for (it=cnt.begin();it!=cnt.end();it++)
	{
		pair<int,int> p=(*it).first;
		if (cnt[p]>0) e.push_back((edge){p.first,p.second,last[p],m});
	}
	for (int i=1;i<=n;i++) father[i]=i,siz[i]=1;
	solve(1,m,e);
	for (int i=1;i<=m;i++)
		if (q[i].x) 
			if (ans[i]) puts("Y");else puts("N");
	return 0;
}