P4785 [BalticOI 2016 Day2]交换

pitiless0514 · 2022-10-06 08:29:04 · 题解

Statement

一个长度为 n 的排列，可以通过交换修改这个序列，你可以执行连续 n-1 轮操作，操作编号 k 为 2 \sim n，每次你可以交换 a_k 和 a_{\lfloor \frac{k}{2} \rfloor} 或者什么都不干。

要求最小化字典序，n \leq 2 \times 10^5。

Solution

题目的操作很有特性，看到 x 和 \lfloor \dfrac{x}{2} \rfloor，联想到线段树的标号，于是先将其给定的序列建成一颗二叉树，在二叉树上考虑问题。

考虑当前在点 u，设他的值为 a，他左儿子 u \times 2 值为 b，右儿子 u \times 2 + 1 值为 c。

那么注意到按照操作顺序，u 的值要变化，要么只能是由祖先进行替换，或者是由 b, c 进行替换。

于是大力分类讨论。

当 a < \min\{b, c\} 的时候，b, c 都没 a 小，让他们靠前字典序只会增大，于是 u 节点不交换，递归两个儿子处理儿子就好了。

当 b < \min\{a, c\} 的时候，此时交换 a, b 让 u 节点的值最小，从而可以让字典序最小。

接下来观察子节点 ls(u), rs(u) 的顺序，现在是 a, c，但是有没有可能，会为 c, a？

一定不可能，因为交换 (ls(u), u) 的时间为 u \times 2，交换 (rs(u), u) 的时间为 u \times 2 + 1，所以只能先交换左节点，而后面假如交换 (rs(u), u)，会让点 u 的值变为 c，与最优字典序不符，所以此情况子节点顺序只能为 a, c，继续递归两个儿子计算即可。

当 c < \min\{b, c\} 的时候，这个时候交换 a, c 让 u 节点的值最小，才能最小化字典序，但是子节点内的顺序，有可能是 a, b 也有可能是 b, a 这个时候两种情况都有可能，并不确定哪边会更优。

不失一般性假设 a < b，假如 a 放到左子树的最后位置为 p，那么将 b 放到左子树来，位置 p 的值一定会增大，因为我们会优先让字典序更小，也就是小的在前面，此时更小的 a 都只能到位置 p，而更大的 b 自然无法到 p 以前，所以位置 p 的值一定会增大，右子树情况同理。

所以我们可以在写一个爆搜，同样按照我们上面的三条策略，搜出 a 在左子树的位置 p1 和右子树的位置 p2，之后看一下 p1, p2 谁更小，就让 b 走小的那边就好了。

然后爆搜写的是 (u, v, id) 表示当前在点 u，将 u 的值变成 v，然后上一步来自 id 的最优能到达的位置。

记得在爆搜中第三种情况的时候讨论一下 b 和 v 的大小，假如是 b 小一点，就让 v 走 b 左右子树分别走之后最终返回位置大的那一边，因为要最优化整个字典序，而不是单个字典序，b 更小，要先优化它的位置。

复杂度的话，注意到假如访问到一个点 u，爆搜中可能出现的 v 一定会是它的祖先或者某个祖先的兄弟，于是合法的 {u, v} 二元组只有 \log 个，记忆化一下，复杂度就对了。

代码用 map 实现的，总复杂度就为 O(n \log^2 n)。

// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
// 德丽莎的可爱在于德丽莎很可爱，德丽莎为什么很可爱呢，这是因为德丽莎很可爱！
// 没有力量的理想是戏言，没有理想的力量是空虚
#include <bits/stdc++.h>
#define LL long long
using namespace std;
char ibuf[1 << 15], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++)
inline int read() {
  char ch = getchar();  int x = 0, f = 1;
  while (ch < '0' || ch > '9')  {  if (ch == '-')  f = -1;  ch = getchar();  }
  while (ch >= '0' && ch <= '9')  x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return x * f;
}
void print(LL x) {
  if (x > 9)  print(x / 10);
  putchar(x % 10 + '0');
}
template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define repd(i, l, r) for (int i = (l); i >= (r); i--)
#define REP(i, l, r)  for (int i = (l); i < (r); i++)
const int N = 2e6;
int n, p[N];
int ls(int p) {  return p << 1;  }
int rs(int p) {  return p << 1 | 1;  }
map < pair<int,int>,int> mp;
int find(int u,int v,int id) {
  if (u > n)  return id;
  if (mp.find({u, v}) != mp.end())  return mp[{u, v}];
  int &b = p[ls(u)], &c = p[rs(u)], &w = mp[{u, v}];
  if (v < min(b, c))  return w = u;
  if (b < c)  return w = find(ls(u), v, u);
  else if (b < v) {
    int lans = find(ls(u), b, u);
    int rans = find(rs(u), b, u);
    if (lans > rans) {
      return w = find(ls(u), v, u);
    } else {
      return w = find(rs(u), v, u);
    }
  } else {
    return w = min(find(u << 1, v, u), find(u << 1 | 1, v, u));
  }
}
void work(int u) { 
  if (u > n)  return;
  int &a = p[u], &b = p[ls(u)], &c = p[rs(u)];
  if (a < min(b, c)) {
    work(ls(u));
    work(rs(u));
    return;
  }
  if (b < c) {
    swap(a, b);
    work(ls(u));
    work(rs(u));
    return;
  }
  swap(a, c);
  if (b > c)  swap(b, c);
  if (find(ls(u), b, ls(u)) > find(rs(u), b, rs(u)))  swap(b, c);
  work(ls(u));
  work(rs(u));
}
void solve() {
  n = read();
  rep (i, 1, n)  p[i] = read();
  rep (i, n + 1, 2 * n + 1)  p[i] = n + 1;
  work(1);
  rep (i, 1, n)  cout << p[i] << " ";
}
signed main () {
#ifdef LOCAL_DEFINE
  freopen("1.in", "r", stdin);
  freopen("1.ans", "w", stdout);
#endif
  int T = 1;  while (T--)  solve();
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}