题意
给出一个某些位置不全的欧拉序，求出一个符合条件的，或输出不行
传送门
(n le 5*10^5)
思路
终于不是一道神仙(dp)
变成了一道神仙构造
以下简称两相同数围成的是一个区间，基本性质：
- 两个相同数之间的长度为奇数
- 头尾一定相同
- 区间要么完全包含要么不相交
- 某段区间内已确定的落单的数一定小于区间(0)的个数(+1)，因为一个落单的数除了叶子总得再配一个
- 对任意一棵大小为(x)的子树，序列长度为(2x-1)
首先区间不相交就让我们可以分治搞下去，先递归到最小的区间处理，然后处理完此区间对答案就没有影响了，可以直接删掉（浓缩成一个根节点代替整个子树），具体就是维护一下前驱和后继循环时一段一段跳就好了。
接着要考虑最小的区间怎么办了。考虑一下填完后确定的数一定是(lfloor frac{区间长度+1}2
floor)，那么首先从前往后在多出来的空格填未出现过的数字。
接着就开始了，形如(120)或(021)的，只要填成(121),也就是我们要不停的找如(xy0)或(0xy)的某三个数，并且填完后把它们当做只有(2)也就是父亲节点就好了。
如果还有是没填的怎么办呢？发现当前区间的父亲可以用来分割两个区间。
例如填完后变成了(1[20304]1)括号表示当前区间，无法用前面的方法再来填，那就可以用(1)来填补剩下的空格变为(1213141)
#include <bits/stdc++.h>
using std::deque;
const int N=1000100;
int suf[N],pre[N],Next[N],last[N],c[N],a[N],n,m,now;
struct note{
int x,p;
};
deque <note> q;
void endd(){
puts("no");
exit(0);
}
void del(int x,int y){
suf[x]=suf[y];
pre[suf[y]]=x;
}
int get(){
while (c[now]) now++;
if (now>n) endd();
c[now]=1;
return now;
}
void solve(int l,int r){
if (r<l) return;
if ((r-l)&1) endd();
for (int i=l;i<=r;i=suf[i]){
if (!a[i]) continue;
while (Next[i]){
int to=Next[i];
if (to>r) endd();
solve(suf[i],pre[to]);
del(i,to);
Next[i]=Next[to];
}
}
int sum=0,sum0=0;
for (int i=l;i<=r;i=suf[i]){
sum+=(a[i]>0);
sum0+=(!a[i]);
}
if (sum0<sum-1) endd();
for (int i=l;i<=r && sum0>sum;i=suf[i])
if (!a[i]) a[i]=get(),sum0--,sum++;
int rt=a[pre[l]];
for (int i=l;suf[i]<=r;i=suf[i]){
while (i>l && suf[i]<=r && a[i] && a[suf[i]] && (!a[pre[i]])){
a[pre[i]]=a[suf[i]];
del(pre[i],suf[i]);
i=pre[pre[i]];
}
while (i>=l && suf[suf[i]]<=r && a[i] && a[suf[i]] && (!a[suf[suf[i]]])){
a[suf[suf[i]]]=a[i];
del(i,suf[suf[i]]);
i=pre[i];
}
}
for (int i=l;i<=r;i=suf[i])
if (!a[i]) a[i]=rt;
}
int main(){
scanf("%d",&n);
m=2*n-1;
for (int i=1;i<=m;i++) scanf("%d",&a[i]),c[a[i]]++;
if (a[1]!=a[2*n-1] && a[1] && a[2*n-1]) endd();
a[1]=a[m]=(a[1]|a[m]);
for (int i=m;i>=1;i--)
Next[i]=last[a[i]],last[a[i]]=i;
now=1;
suf[0]=1;
for (int i=1;i<=m;i++) pre[i]=i-1,suf[i]=i+1;
solve(1,m);
puts("yes");
for (int i=1;i<=m;i++) printf("%d ",a[i]);
}
后记
神仙啊，其实我还是不怎么懂