「CF1053E」Euler tour
「CF1053E」Euler tour

2019 年 05 月 09 日

给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。

n≤5×105,∣S∣=2n−1n \leq 5 \times 10^5, |S| = 2n - 1。

题解

主体思路

我们可以分治，solve⁡(l,r)\operatorname{solve}(l, r) 表示解决 ll 到 rr 这段区间其中 al=ara_l = a_r。

首先如果 a(l+1)⋯(r−1)a_{(l + 1) \cdots (r - 1)} 中有何 ala_l 相等的数，那么可以继续分治，否则的话中间没有和 ala_l 相等的数。

对于所有满足 l<p<q<r and ap=aql < p < q < r \text{ and } a_p = a_q，也可以递归，递归完后删除掉除了这段区间的根节点的点。这样的话 a(l+1)⋯(r−1)a_{(l + 1) \cdots (r - 1)} 除 00 外互不相同。

接下来考虑对于所有 x,y,0x, y, 0 或 0,y,x0, y, x 的，可以直接把空格处填成 xx，然后缩掉。这样的话只会剩下连续的 00。

对于连续的 00，依次补过去，每补上一个，如果存在 x,y,0x, y, 0 或 0,y,x0, y, x 就继续缩掉。

最后只剩下一个点，也就完成了递归。

对无解的判断

  1. 没有足够的点用来放
  2. a1≠ana_1 \neq a_n
  3. 对于 solve⁡(l,r)\operatorname{solve}(l, r)，r−l+1r - l + 1 是 22 的倍数
  4. 对于 solve⁡(l,r)\operatorname{solve}(l, r)，递归完后 00 的个数小于非 00 个数 −1-1
  5. 存在 p<q<r<sp < q < r < s 满足 ap=ar and aq=as and ap≠aq and ar≠asa_p = a_r \text{ and } a_q = a_s \text{ and } a_p \neq a_q \text{ and } a_r \neq a_s

对于 a1,a2n−1a_1, a_{2n - 1} 的特殊处理

  1. 如果 a1≠0 and a2n−1≠0 and a1≠a2n−1a_1 \neq 0 \text{ and } a_{2n-1} \neq 0 \text{ and } a_1 \neq a_{2n-1}，那么无解
  2. 如果 (a1=0 and a2n−1≠0) or (a1≠0 and a2n−1=0)(a_1 = 0 \text{ and } a_{2n-1} \neq 0) \text{ or } (a_1 \neq 0 \text{ and } a_{2n-1} = 0)，那么 a1=a2n−1=max⁡(a1,a2n−1)a_1 = a_{2n-1} = \max(a_1, a_{2n-1}) 即可
  3. 如果 a1=a2n−1=0a_1 = a_{2n-1} = 0 那么需要给 a1,a2n−1a_1, a_{2n-1} 分配一个标号。先枚举检查有没有可以从中间选出的可能，如果没有，就新分配一个点

对于递归的复杂度保证

直接实现的可能会超时，我把相同值的下标存到一起，然后根据「CTSC2018 青蕈领主」的方式建树，先把区间内与根节点不同色的递归处理掉，再来处理根节点同色的。

对于扫描形如 x,y,0x, y, 0 和 y,x,0y, x, 0 的复杂度保证

可以开一个栈暴力扫过去，用类似括号匹配的方式处理，这里不多讲。

需要注意的是，我的实现是先把已有的 x,y,0x, y, 0 和 y,x,0y, x, 0 填掉，不然有可能不是最优方案。

然后两端同时扫描，如果没有可以直接填的，但给两端中的 00 的点分配标号可以配对的话，就分配掉。如果都没有，随便一端填个数即可。

复杂度证明

一个数只会在某一层被处理掉，对那一层的复杂度贡献是 O(1)\mathcal O(1) 的，所以这一部分的时间复杂度为 O(n)\mathcal O(n)。

由于需要判断无解等等情况，可以写一个支持区间查询最大值 / 最小值的线段树 / ST 表，时间复杂度 O(nlog⁡n)\mathcal O(n \log n)，其中 ST 表的空间复杂度为 O(nlog⁡n)\mathcal O(n \log n)，可能会导致 MLE\text{MLE}。

综上，时间复杂度 O(nlog⁡n)\mathcal O(n \log n)，空间复杂度 O(n)\mathcal O(n)，可以通过本题。

代码

#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];
}

评论

TABLE OF CONTENTS

题解
主体思路
对无解的判断
对于 a1,a2n−1a_1, a_{2n - 1} 的特殊处理
对于递归的复杂度保证
对于扫描形如 x,y,0x, y, 0 和 y,x,0y, x, 0 的复杂度保证
复杂度证明
代码