萌新求助 WA #4

#include<bits/stdc++.h>
using namespace std;
int n,m=1,id1[50004],id2[50004],ct[50004],pos[50004][4],ans[200005];
int tot,head[14400007],to[36000007],nxt[36000007];
int idx,tp,cnt,dfn[14400007],low[14400007],vis[14400007],stk[14400007],scc[14400007];
int k,rt[200005],lc[7200006],rc[7200006],id[7200006],od[7200006];
struct node{int id,l,r;}seg[200005];
bool cmp(node a,node b){return a.l==b.l?a.r>b.r:a.l<b.l;}
void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	vis[u]=1;stk[++tp]=u;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
		else if(vis[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		cnt++;
		for(;;)
		{
			int v=stk[tp--];
			vis[v]=0;scc[v]=cnt;
			if(u==v)break;
		}
	}
}
void add(int u,int v)
{
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
void pushup(int u)
{
	if(lc[u])
	{
		add(id[u],id[lc[u]]);
		add(od[lc[u]],od[u]);
	}
	if(rc[u])
	{
		add(id[u],id[rc[u]]);
		add(od[rc[u]],od[u]);
	}
}
int update(int u,int l,int r,int p,int w)
{
	k++;
	lc[k]=lc[u];rc[k]=rc[u];
	id[k]=++m;od[k]=++m;u=k;
	if(l==r)
	{
		add(id[u],w);
		add(w^1,od[u]);
		return u;
	}
	int mid=l+r>>1;
	if(p<=mid)lc[u]=update(lc[u],l,mid,p,w);
	else rc[u]=update(rc[u],mid+1,r,p,w);
	pushup(u);return u;
}
void query(int u,int l,int r,int L,int R,int w)
{
	if(!u)return;
	if(r<L||l>R)return;
	if(L<=l&&r<=R)
	{
		add(w,id[u]);
		add(od[u],w^1);
		return;
	}
	int mid=l+r>>1;
	query(lc[u],l,mid,L,R,w);
	query(rc[u],mid+1,r,L,R,w);
}
int main()
{
//	freopen("meow.in","r",stdin);
//	freopen("meow.out","w",stdout);
	cin>>n;
	for(int i=1,a;i<=n*4;i++)
	{
		cin>>a;
		pos[a][ct[a]++]=i;
	}
	for(int i=1;i<=n;i++)
	{
		id1[i]=++m;
		seg[i*4-3]=(node){m,pos[i][0],pos[i][1]};
		seg[i*4-2]=(node){m,pos[i][2],pos[i][3]};
		id2[i]=++m;
		seg[i*4-1]=(node){m,pos[i][0],pos[i][2]};
		seg[i*4]=(node){m,pos[i][1],pos[i][3]};
	}
	sort(seg+1,seg+n*4+1,cmp);
	for(int i=1;i<=n*4;i++)
	{
		query(rt[i-1],1,n*4,seg[i].r,n*4,seg[i].id);
		rt[i]=update(rt[i-1],1,n*4,seg[i].r,seg[i].id^1);
	}
	for(int i=1;i<=m;i++)if(!vis[i])tarjan(i);
	for(int i=1;i<=n;i++)
	{
		if(scc[id1[i]]==scc[id2[i]]){cout<<"No\n";return 0;}
		if(scc[id1[i]]<scc[id2[i]])
		{
			ans[pos[i][0]]=ans[pos[i][2]]=0;
			ans[pos[i][1]]=ans[pos[i][3]]=1;
		}
		else
		{
			ans[pos[i][0]]=ans[pos[i][1]]=0;
			ans[pos[i][2]]=ans[pos[i][3]]=1;
		}
	}
	cout<<"Yes\n";
	for(int i=1;i<=4*n;i++)cout<<ans[i];
}