给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。
。
题解
主体思路
我们可以分治， 表示解决 到 这段区间其中 。
首先如果 中有何 相等的数，那么可以继续分治，否则的话中间没有和 相等的数。
对于所有满足 ，也可以递归，递归完后删除掉除了这段区间的根节点的点。这样的话 除 外互不相同。
接下来考虑对于所有 或 的，可以直接把空格处填成 ，然后缩掉。这样的话只会剩下连续的 。
对于连续的 ，依次补过去，每补上一个，如果存在 或 就继续缩掉。
最后只剩下一个点，也就完成了递归。
对无解的判断
- 没有足够的点用来放
- 对于 ， 是 的倍数
- 对于 ，递归完后 的个数小于非 个数
- 存在 满足
对于 的特殊处理
- 如果 ，那么无解
- 如果 ，那么 即可
- 如果 那么需要给 分配一个标号。先枚举检查有没有可以从中间选出的可能，如果没有，就新分配一个点
对于递归的复杂度保证
直接实现的可能会超时，我把相同值的下标存到一起，然后根据「CTSC2018 青蕈领主」的方式建树，先把区间内与根节点不同色的递归处理掉，再来处理根节点同色的。
对于扫描形如 和 的复杂度保证
可以开一个栈暴力扫过去，用类似括号匹配的方式处理，这里不多讲。
需要注意的是，我的实现是先把已有的 和 填掉，不然有可能不是最优方案。
然后两端同时扫描，如果没有可以直接填的，但给两端中的 的点分配标号可以配对的话，就分配掉。如果都没有，随便一端填个数即可。
复杂度证明
一个数只会在某一层被处理掉，对那一层的复杂度贡献是 的，所以这一部分的时间复杂度为 。
由于需要判断无解等等情况，可以写一个支持区间查询最大值 / 最小值的线段树 / ST 表，时间复杂度 ，其中 ST 表的空间复杂度为 ，可能会导致 。
综上，时间复杂度 ，空间复杂度 ，可以通过本题。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9, L = 21;
int n, m, a[N], del[N], use[N], lg[N];
vector<int> v[N], G[N];
struct info {
int val, id;
inline info() {}
inline info(int k) { val = a[k], id = k; }
inline info(int a, int b) { val = a, id = b; }
};
vector<info> s, h, t, bkt[N];
priority_queue<int, vector<int>, greater<int>> q;
void noSolution() { puts("no"), exit(0); }
struct minimax {
int min, max;
inline minimax operator^(const minimax &other) const { return {std::min(min, other.min), std::max(max, other.max)}; }
} b[N];
struct segment {
int l, r, mid;
minimax x;
} p[N << 2];
void build(int u, int l, int r) {
p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
if (l == r) {
p[u].x = b[l];
return;
}
build(u << 1, l, p[u].mid);
build(u << 1 | 1, p[u].mid + 1, r);
p[u].x = p[u << 1].x ^ p[u << 1 | 1].x;
}
minimax query(int u, int l, int r) {
if (p[u].l == l && p[u].r == r) return p[u].x;
if (r <= p[u].mid) return query(u << 1, l, r);
else if (l > p[u].mid)
return query(u << 1 | 1, l, r);
else
return query(u << 1, l, p[u].mid) ^ query(u << 1 | 1, p[u].mid + 1, r);
}
void init() {
static int tmp[N];
memset(tmp, 0, sizeof tmp);
for (int i = 1; i <= m; i++)
if (a[i]) {
if (!tmp[a[i]]) tmp[a[i]] = i;
b[i].min = tmp[a[i]];
} else {
b[i].min = i;
}
memset(tmp, 0, sizeof tmp);
for (int i = m; i >= 1; i--)
if (a[i]) {
if (!tmp[a[i]]) tmp[a[i]] = i;
b[i].max = tmp[a[i]];
} else {
b[i].max = i;
}
build(1, 1, m);
}
minimax query(int l, int r) { return query(1, l, r); }
inline bool possible(int l, int r) {
if (!((r - l + 1) & 1)) return false;
if (l + 1 > r - 1) return true;
auto it = query(l + 1, r - 1);
return it.max <= r && it.min >= l;
}
inline int newNode() {
static int cur = 1;
while (use[cur]) cur++;
if (cur > n) cerr << "[No enougth nodes] No solution.\n", noSolution();
return use[cur] = 1, cur;
}
void solve(int x) {
vector<pair<int, int>> jump;
for (auto y : G[x]) {
solve(y);
jump.push_back(make_pair(*v[y].begin(), *--v[y].end()));
}
reverse(jump.begin(), jump.end());
for (int i = 0, L, R, at = 0; i + 1 < v[x].size(); i++) {
L = v[x][i], R = v[x][i + 1];
if (!((R - L + 1) & 1)) noSolution(); // 要求每个这样的区间为奇数
s.clear(), s.push_back(info(L));
for (int i = L + 1; i <= R - 1; i++) {
s.push_back(info(i));
if (at < jump.size() && i == jump[at].first) i = jump[at++].second;
}
s.push_back(info(R));
int c0 = 0, c1 = 0;
for (int i = 1; i + 1 < s.size(); i++) s[i].val ? ++c1 : ++c0;
if (c0 < c1 - 1) noSolution();
int tl = 0, tr = s.size() - 1;
while (tl < s.size() && s[tl].val) tl++;
while (tr >= 0 && s[tr].val) tr--;
if (tl == s.size()) continue;
for (int i = tl; i <= tr; i++)
if (s[i].val) {
if (t.size() >= 2 && (--t.end())->val && !(-- --t.end())->val) {
a[(-- --t.end())->id] = s[i].val;
del[(-- --t.end())->id] = del[(--t.end())->id] = 1;
t.pop_back(), t.pop_back(), t.push_back(s[i]);
} else {
t.push_back(s[i]);
}
} else {
if (t.size() >= 2 && (--t.end())->val && (-- --t.end())->val) {
a[s[i].id] = (-- --t.end())->val;
del[s[i].id] = del[(--t.end())->id] = 1;
t.pop_back();
} else {
t.push_back(s[i]);
}
}
t.clear(), swap(t, s);
for (int i = 0; i < t.size(); i++)
if (del[t[i].id]) del[t[i].id] = false;
else
s.push_back(t[i]);
t.clear();
for (int i = 0, j = s.size() - 1; i <= j;) {
if (s[i].val) {
h.push_back(s[i++]);
} else if (s[j].val) {
t.push_back(s[j--]);
} else {
if (h.size() >= 2) {
a[s[i].id] = s[i].val = (-- --h.end())->val;
h.pop_back(), i++;
} else if (t.size() >= 2) {
a[s[j].id] = s[j].val = (-- --t.end())->val;
t.pop_back(), j--;
} else {
a[s[i].id] = s[i].val = newNode();
h.push_back(s[i++]);
}
}
}
h.clear(), t.clear(), s.clear();
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
m = (n << 1) - 1, lg[0] = -1;
for (int i = 1; i <= m; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= m; i++) {
cin >> a[i];
if (a[i]) use[a[i]] = 1;
}
if (a[1] && a[m] && a[1] != a[m]) noSolution();
else if (!a[1] && !a[m]) {
init();
int any = 0;
for (int i = 3; i <= m - 2; i++) {
if (a[i] && a[i] != a[2] && a[i] != a[m - 1] && possible(1, i) && possible(i, m)) any = max(any, a[i]);
}
a[1] = a[m] = any ? any : newNode();
} else
a[1] = a[m] = a[1] | a[m];
init();
for (int i = 1; i <= m; i++)
if (a[i]) v[a[i]].push_back(i);
for (int i = 1; i <= n; i++)
if (v[i].size() > 1) {
for (int j = 0; j + 1 < v[i].size(); j++)
if (!possible(v[i][j], v[i][j + 1])) {
cerr << "[Impossible section] " << v[i][j] << " " << v[i][j + 1] << endl;
noSolution();
}
bkt[*--v[i].end()].push_back({*v[i].begin(), i});
}
for (int i = 1; i <= m; i++) {
for (auto it : bkt[i]) {
while (s.size() && (--s.end())->val >= it.val) {
G[it.id].push_back((--s.end())->id);
s.pop_back();
}
s.push_back(it);
}
}
s.clear();
solve(a[1]);
cout << "yes" << endl;
for (int i = 1; i <= m; i++) cout << a[i] << " \n"[i == m];
}