Codeforces Gym 103627D Two Bullets

发表于 | 分类于 | 66

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

建图，对于逆序对 i<j,Ai>Aj 连边 i→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(log2n)，总共 O(nlog3n)。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#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);
}

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!