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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;
int n, m;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct Splay {
int v, key, k, ch[2], sz;
} T[maxn]; int rt, top, f[maxn];
inline int get(int i) { return T[f[i]].ch[1] == i; }
inline int newnode(int v, int k) {
int i = ++top;
return T[i] = { v, v, k, 0, 0, 1 }, i;
}
inline void update(int i) {
T[i].sz = T[lc].sz + T[rc].sz + 1;
T[i].v = max({ T[i].key, T[lc].v, T[rc].v });
}
inline void rotate(int x) {
int fa = f[x], ffa = f[f[x]], wx = get(x);
f[fa] = x; f[x] = ffa; f[T[x].ch[wx ^ 1]] = fa;
if (ffa) T[ffa].ch[T[ffa].ch[1] == fa] = x;
T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
update(fa); update(x);
}
void Splay(int i, int k = 0) {
for (int fa = f[i]; fa != k; rotate(i), fa = f[i])
if (f[fa] != k) rotate(get(fa) == get(i) ? fa : i);
if (!k) rt = i;
}
void insert(int &rt, int fa, int v, int k) {
int i = rt, d;
if (!rt) return rt = newnode(v, k), f[rt] = fa, Splay(rt);
while (1) {
d = max(T[i].key, T[rc].v) >= v;
if (!T[i].ch[d])
return T[i].ch[d] = newnode(v, k), f[T[i].ch[d]] = i, Splay(T[i].ch[d]);
i = T[i].ch[d];
}
}
int findk(int k) {
int i = rt;
while (1) {
if (k <= T[lc].sz) { i = lc; continue; }
k -= T[lc].sz;
if (k <= 1) return Splay(i), i;
--k; i = rc;
}
}
void dfs(int i) {
if (!i) return ;
dfs(lc);
cout << T[i].k << " ";
dfs(rc);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
int x, y; cin >> x >> y;
if (y >= i - 1) insert(rt, 0, x, i);
else findk(i - 1 - y), insert(T[rt].ch[1], rt, x, i);
} dfs(rt);
return 0;
}
|