考虑如果每个数恰好出现两次,那么容易得出一个序列合法当且仅当将每个数两次出现位置看作一个区间 \([l_i,r_i]\) 的两个端点,那么这些区间两两之间不存在包含关系。
考虑每个数出现四次的情况,我们钦定两次为 \(i\),两次为 \(i+n\),这样可以转化为 \(2n\) 的情况,而容易发现只有 \(1122\) 和 \(1212\) 两种情况,因为 \(1221\) 本身就出现包含关系了,而这容易让我们想到 2-SAT 的模型,区间不能包含又意味着有一些 \(p\to q\) 的关系,于是 2-SAT 做即可,限制关系可以看作一个矩形,使用主席树优化建图解决。
const int MAXN=2e5;
const int MAXV=1e7;
const int MAXE=5e7;
int n,a[MAXN+5];vector<int>pos[MAXN+5];
int hd[MAXV+5],to[MAXE+5],nxt[MAXE+5],ec;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int rev(int x){return (x>n)?(x-n):(x+n);}
struct node{int ch[2],n1,n2;}s[MAXV+5];
int ncnt,rt[MAXN+5],ptcnt;
int modify(int k,int l,int r,int p,int pt1,int pt2){
int z=++ncnt;s[z]=s[k];s[z].n1=++ptcnt;s[z].n2=++ptcnt;
if(l==r){adde(s[z].n1,pt1);adde(pt2,s[z].n2);return z;}
int mid=l+r>>1;
if(p<=mid)s[z].ch[0]=modify(s[k].ch[0],l,mid,p,pt1,pt2);
else s[z].ch[1]=modify(s[k].ch[1],mid+1,r,p,pt1,pt2);
if(s[z].ch[0])adde(s[z].n1,s[s[z].ch[0]].n1),adde(s[s[z].ch[0]].n2,s[z].n2);
if(s[z].ch[1])adde(s[z].n1,s[s[z].ch[1]].n1),adde(s[s[z].ch[1]].n2,s[z].n2);
return z;
}
void connect(int k,int l,int r,int ql,int qr,int p1,int p2){
if(ql>qr||!k)return;
if(ql<=l&&r<=qr){adde(p1,s[k].n1);adde(s[k].n2,p2);return;}
int mid=l+r>>1;
if(qr<=mid)connect(s[k].ch[0],l,mid,ql,qr,p1,p2);
else if(ql>mid)connect(s[k].ch[1],mid+1,r,ql,qr,p1,p2);
else connect(s[k].ch[0],l,mid,ql,mid,p1,p2),connect(s[k].ch[1],mid+1,r,mid+1,qr,p1,p2);
}
int dfn[MAXV+5],low[MAXV+5],stk[MAXV+5],bel[MAXV+5],tp,cmp,tim,vis[MAXV+5];
vector<pii>vec[MAXN+5];
void tarjan(int x){
dfn[x]=low[x]=++tim;stk[++tp]=x;vis[x]=1;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];
if(!dfn[y])tarjan(y),chkmin(low[x],low[y]);
else if(vis[y])chkmin(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
cmp++;int o;
do{o=stk[tp--];vis[o]=0;bel[o]=cmp;}while(o^x);
}
}
int res[MAXN+5];
int main(){
scanf("%d",&n);ptcnt=2*n;
for(int i=1;i<=n*4;i++)scanf("%d",&a[i]),pos[a[i]].pb(i);
for(int i=1;i<=n;i++){
vec[pos[i][0]].pb(mp(pos[i][1],i));
vec[pos[i][2]].pb(mp(pos[i][3],i));
vec[pos[i][0]].pb(mp(pos[i][2],i+n));
vec[pos[i][1]].pb(mp(pos[i][3],i+n));
}
for(int i=1;i<=n*4;i++){
rt[i]=rt[i-1];
for(pii p:vec[i])rt[i]=modify(rt[i],1,n*4,p.fi,rev(p.se),p.se);
for(pii p:vec[i])connect(rt[i-1],1,n*4,p.fi,n*4,p.se,rev(p.se));
}
for(int i=1;i<=ptcnt;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)if(bel[i]==bel[i+n])return puts("No"),0;
for(int i=1;i<=n;i++){
if(bel[i]<bel[i+n])res[pos[i][1]]=res[pos[i][3]]=1;
else res[pos[i][2]]=res[pos[i][3]]=1;
}
puts("Yes");
for(int i=1;i<=n*4;i++)printf("%d",res[i]);
return 0;
}
/*
2
1 2 2 2 2 1 1 1
*/
标签:洛谷,THUPC,int,MAXV,mid,初赛,++,MAXN,low
From: https://www.cnblogs.com/tzcwk/p/luogu-P9139.html