Codeforces Gym 103627D. Two Bullets

牛逼论文题，但或许也可以猜。

建图，对于逆序对 \(i < j, A_i > A_j\) 连边 \(i \to j\)。这也叫做排列图（Permutation Graph）。则每次就是删去最多两个入度为 \(0\) 的点。

对于任意 DAG，有论文给出了这样一个方法：

首先，找到一个特殊的拓扑序。像一般的拓扑排序那样，每次删去一个入度为 \(0\) 的点并加到拓扑序中。
但此处，如果有多个入度为 \(0\) 的点，设 \(N(v)\) 为 \(v\) 的入边被删除的时间的集合。我们将每个 \(N(v)\) 中的元素降序排列后寻找字典序最小的 \(N(v)\)（换句话说，尽可能早地被减小入度的 \(v\)），并在这一轮中选择 \(v\)。
然后，逆着拓扑序反着求答案。每次取两个在拓扑序中最靠后的，出度为 \(0\) 的点删去，并加到答案的前端。

这样我们就至少获得了一个多项式时间的做法。考虑在排列图上如何优化之。

首先，计算出 \(level(i)\) 表示以 \(i\) 结尾的最长路。也就是以 \(i\) 结尾的最长下降子序列长度。
我们按照 \(level(i)\) 升序处理所有点，不难发现这样和拓扑排序是等价的，且同层间没有连边。

那么，分层做，我们只需要支持对任意 \(v,w\) 比较 \(N(v),N(w)\) 的字典序即可。由于已经降序，所以我们事实上只需要比较 \(N(v)-N(w),N(w)-N(v)\) 中的最大值。
这是单点修改，矩形 \(\max\)，用树套树即可做到单次 \(O(\log^2 n)\)，总共 \(O(n\log^3 n)\)。

还是有点慢，但我们发现如果我们需要先求这个 3-side 矩形中点的最大 \(level(i)\)（这是静态的），是可以用主席树 \(O(n\log n)\) 预处理 \(O(\log n)\) 查询的（不过原论文好像用的是划分树状物，可能这就是学术界做法吧）。
而同 \(level\) 的点一定是反链，所以可以转化为区间 \(\max\) 查询。
这样就做到了 \(O(n\log^2 n)\)。

但是这似乎还是太 naive。
（似乎）可以观察到最小时间等于 \(N\) 减去补图的最大匹配。进一步，有论文证明了本题的答案和补图的最大匹配是双射（具体的映射应该很好猜），那么我们对于一组最大匹配只需要一直找入度为 \(0\) 的点就可以排出一个操作顺序。这是 \(O(n\log n)\) 的。
而目前有论文声称可以在 \(O(n\log \log n)\) 时间内计算排列图（显然排列图的补图也是排列图）的最大匹配，感觉很 nb。

代码（实现了 \(3\log\) 的做法）：

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 0x3f3f3f3f;
 
const int N = 1e5;
 
int n, p[N + 5], q[N + 5];
int level[N + 5];
int a[N + 5], b[N + 5];
 
struct BinaryIndexedTree {
  int c[N + 5];
  void update(int x, int k) {
    for (; x; x &= x - 1) c[x] = max(c[x], k);
  }
  int query(int x) {
    int ret = 0;
    for (; x <= n; x += x & -x) ret = max(ret, c[x]);
    return ret;
  }
} bit;
 
struct TreeOfTree {
  struct segnode {
    int max;
    int ls, rs;
  } seg[N * 700 + 5];
  void insert(int x, int k, int &u, int tl, int tr) {
    static int tot = 0;
    if (!u) u = ++tot;
    seg[u].max = max(seg[u].max, k);
    if (tl == tr) return ;
    int mid = (tl + tr) >> 1;
    if (x <= mid) insert(x, k, seg[u].ls, tl, mid);
    else insert(x, k, seg[u].rs, mid + 1, tr);
  }
  int query(int l, int r, int u, int tl, int tr) {
    if (!u || (l <= tl && tr <= r)) return seg[u].max;
    int mid = (tl + tr) >> 1;
    int ret = 0;
    if (l <= mid) ret = max(ret, query(l, r, seg[u].ls, tl, mid));
    if (r > mid) ret = max(ret, query(l, r, seg[u].rs, mid + 1, tr));
    return ret;
  }
  #define ls (u << 1)
  #define rs (ls | 1)
  int rt[N * 4 + 5];
  void insert(int x, int y, int k, int u, int tl, int tr) {
    insert(y, k, rt[u], 1, n);
    if (tl == tr) return ;
    int mid = (tl + tr) >> 1;
    if (x <= mid) insert(x, y, k, ls, tl, mid);
    else insert(x, y, k, rs, mid + 1, tr);
  }
  void insert(int x, int y, int k) { insert(x, y, k, 1, 1, n); }
  int query(int l, int r, int x, int y, int u, int tl, int tr) {
    if (l <= tl && tr <= r) return query(x, y, rt[u], 1, n);
    int mid = (tl + tr) >> 1;
    int ret = 0;
    if (l <= mid) ret = max(ret, query(l, r, x, y, ls, tl, mid));
    if (r > mid) ret = max(ret, query(l, r, x, y, rs, mid + 1, tr));
    return ret;
  }
  int query(int l, int r, int x, int y) { return l <= r && x <= y ? query(l, r, x, y, 1, 1, n) : 0; }
  #undef ls
  #undef rs
} tr;
 
struct SegmentTree {
  #define ls (u << 1)
  #define rs (ls | 1)
  struct node {
    int min;
    bool vis, tag;
  } seg[N * 4 + 5];
  void build(int u, int tl, int tr) {
    if (tl == tr) { seg[u].min = p[tl]; return ; }
    int mid = (tl + tr) >> 1;
    build(ls, tl, mid), build(rs, mid + 1, tr);
    seg[u].min = min(seg[ls].min, seg[rs].min);
  }
  void build() { build(1, 1, n); }
  int prev(int x, int u, int tl, int tr) {
    if (seg[u].min >= p[x]) return 0;
    if (tl == tr) return tl;
    int mid = (tl + tr) >> 1;
    if (x <= mid) return prev(x, ls, tl, mid);
    int ret = prev(x, rs, mid + 1, tr);
    if (!ret) ret = prev(x, ls, tl, mid);
    return ret;
  }
  int prev(int x) { return prev(x, 1, 1, n); }
  void pushDown(int u) {
    if (seg[u].tag) {
      seg[ls].vis = 0, seg[ls].tag = 1;
      seg[rs].vis = 0, seg[rs].tag = 1;
      seg[u].tag = 0;
    }
  }
  void undo(int l, int r, int u, int tl, int tr) {
    seg[u].vis = 0;
    if (l <= tl && tr <= r) { seg[u].tag = 1; return ; }
    pushDown(u);
    int mid = (tl + tr) >> 1;
    if (l <= mid) undo(l, r, ls, tl, mid);
    if (r > mid) undo(l, r, rs, mid + 1, tr);
  }
  void undo(int l, int r) { undo(l, r, 1, 1, n); }
  void erase(int x, int u, int tl, int tr) {
    if (tl == tr) { seg[u].min = inf; return ; }
    int mid = (tl + tr) >> 1;
    if (x <= mid) erase(x, ls, tl, mid);
    else erase(x, rs, mid + 1, tr);
    seg[u].min = min(seg[ls].min, seg[rs].min);
  }
  void erase(int x) {
    int y = prev(x, 1, 1, n);
    undo(y + 1, x, 1, 1, n), erase(x, 1, 1, n);
  }
  void search(vector<int> &ret, int rmin, int u, int tl, int tr) {
    if (seg[u].min >= rmin || seg[u].vis) return ;
    seg[u].vis = 1;
    if (tl == tr) { ret.push_back(tl); return ; }
    pushDown(u);
    int mid = (tl + tr) >> 1;
    search(ret,  rmin, rs, mid + 1, tr);
    search(ret, min(rmin, seg[rs].min), ls, tl, mid);
  }
  vector<int> search() {
    vector<int> ret;
    search(ret, inf, 1, 1, n);
    return ret;
  }
  #undef ls
  #undef rs
} seg;
 
vector<pair<int, int>> ans;
priority_queue<int> que;
 
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", p + i), q[p[i]] = i;
  for (int i = 1; i <= n; ++i)
    bit.update(p[i], (level[i] = bit.query(p[i] + 1)) + 1);
  iota(a + 1, a + n + 1, 1), sort(a + 1, a + n + 1, [](int x, int y) { return level[x] < level[y]; });
  for (int l = 1, r; l <= n; l = r + 1) {
    for (r = l; r < n && level[a[r + 1]] == level[a[l]]; ++r);
    sort(a + l, a + r + 1, [](int x, int y) {
      bool flag = 0;
      if (x > y) flag = 1, swap(x, y);
      int a = tr.query(1, x - 1, p[x] + 1, p[y]), b = tr.query(x + 1, y - 1, p[y] + 1, n);
      return a != b ? (a < b) ^ flag : 0;
    });
    for (int i = l; i <= r; ++i) tr.insert(a[i], p[a[i]], i);
  }
  for (int i = 1; i <= n; ++i) b[a[i]] = i;
  seg.build();
  for (;;) {
    auto res = seg.search();
    for (int i: res) que.push(b[i]);
    if (que.empty()) break;
    int x = que.top(); que.pop(), seg.erase(a[x]);
    int y = x;
    if (!que.empty()) y = que.top(), que.pop(), seg.erase(a[y]);
    ans.emplace_back(p[a[x]], p[a[y]]);
  }
  reverse(ans.begin(), ans.end());
  printf("%d\n", ans.size());
  for (auto i: ans) printf("%d %d\n", i.first, i.second);
}

『My guiding star.』

Codeforces Gym 103627D Two Bullets