记录编号	359767	评测结果	AAAAAAATTA
题目名称	[SHOI 2008]堵塞的交通traffic	最终得分	80
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	3.526 s
提交时间	2016-12-24 18:12:44	内存使用	20.14 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int maxn=100010;
inline int randint(){
	static int a=151,b=24863,c=9788417,x=1089488183,p=998244353;
	x=a*x*x+b*x+c;x%=p;
	return x<0?(x=-x):x;
}
struct A{int u,v,tp;}a[maxn];
void addedge(int,int,int);
void addquery(int,int,int);
void solve(int,int,int);
int findroot(int);
void mergeset(int,int,vector<int>&);
int id[3][maxn],cnt=0,prt[maxn<<1],qu[maxn<<2],qv[maxn<<2];
int n,m=1,x1,y1,x2,y2,x,y,s,t;
vector<int>u[maxn<<2],v[maxn<<2],stk[maxn<<2];
map<pair<int,int>,int>mp;
char c[15];
int main(){
	freopen("bzoj_1018.in","r",stdin);
	freopen("bzoj_1018.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		id[1][i]=++cnt;
		id[2][i]=++cnt;
	}
	for(int i=1;i<=cnt;i++)prt[i]=i;
	for(int &i=m;scanf("%s",c)==1&&strcmp(c,"Exit");i++){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		x=id[x1][y1];y=id[x2][y2];
		if(x>y)swap(x,y);
		a[i].u=x;a[i].v=y;
		if(!strcmp(c,"Open"))a[i].tp=1;
		else if(!strcmp(c,"Close"))a[i].tp=2;
		else a[i].tp=3;
	}
	for(int i=1;i<=m;i++){
		x=a[i].u;y=a[i].v;
		if(a[i].tp==1){
			if(!mp.count(make_pair(x,y)))mp[make_pair(x,y)]=i;
		}
		else if(a[i].tp==2){
			if(mp.count(make_pair(x,y))){
				s=mp[make_pair(x,y)];
				t=i;
				addedge(1,m,1);
				mp.erase(make_pair(x,y));
			}
		}
		else{
			t=i;
			addquery(1,m,1);
		}
	}
	for(map<pair<int,int>,int>::iterator it=mp.begin();it!=mp.end();it++){
		x=it->first.first;
		y=it->first.second;
		s=it->second;
		t=m;
		addedge(1,m,1);
	}
	solve(1,m,1);
	return 0;
}
void addedge(int l,int r,int rt){
	if(s<=l&&t>=r){
		u[rt].push_back(x);
		v[rt].push_back(y);
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)addedge(l,mid,rt<<1);
	if(t>mid)addedge(mid+1,r,rt<<1|1);
}
void addquery(int l,int r,int rt){
	if(l==r){
		qu[rt]=x;
		qv[rt]=y;
		return;
	}
	qu[rt]|=x;
	int mid=(l+r)>>1;
	if(t<=mid)addquery(l,mid,rt<<1);
	else addquery(mid+1,r,rt<<1|1);
}
void solve(int l,int r,int rt){
	if(!qu[rt])return;
	for(int i=0;i<(int)u[rt].size();i++)mergeset(u[rt][i],v[rt][i],stk[rt]);
	if(l==r)printf(findroot(qu[rt])==findroot(qv[rt])?"Y\n":"N\n");
	else{
		int mid=(l+r)>>1;
		solve(l,mid,rt<<1);
		solve(mid+1,r,rt<<1|1);
	}
	if(!stk[rt].empty())for(int i=(int)stk[rt].size()-1;i>=0;i--)prt[stk[rt][i]]=stk[rt][i];
}
int findroot(int x){
	while(prt[x]!=x)x=prt[x];
	return x;
}
void mergeset(int x,int y,vector<int>&a){
	x=findroot(x);y=findroot(y);
	if(x==y)return;
	if(randint()&1)swap(x,y);
	prt[x]=y;
	a.push_back(x);
}