Codeforces Beta Round #38 G Queue 动态树

发表于 分类于

本题算是比较难想的题目了，比赛的时候想成 Splay 果断悲剧，今晚才突然发现直接用可以合并的树就可以了。

思路是维护一颗二叉树，每次来了一个元素，找到元素对应的位置，注意找到的位置是靠最右边的第一个比它大的元素的位置，如果此元素在 cic_i 步内不能到达，就插入元素到右边第 cic_i 个位置。

动态树的 split 函数表示将树中的第 kk 个和第 k−1k-1 个元素分开，形成两棵树，这样我们将一个单独的结点分别与这两棵树合并，就可以得到新的序列。

最后进行中序遍历得到最后的解，注意树的合并必须用随机算法，否则会使树退化。

我的代码：

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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 1000100;
const int oo = 0x3f3f3f3f;
struct Node {
  int l, r;
  int val, ma, size;
  Node() {
    l = r = 0;
    val = ma = size = 0;
  }
} node[MAX];

int find(int k, int val) {
  if (k == 0) {
    return 0;
  }
  if (val <= node[node[k].r].ma) {
    return node[node[k].l].size + 1 + find(node[k].r, val);
  } else if (val <= node[k].val) {
    return node[node[k].l].size + 1;
  } else {
    return find(node[k].l, val);
  }
}

void update(int k) {
  node[k].size = node[node[k].l].size + node[node[k].r].size + 1;
  node[k].ma = max(node[k].val, max(node[node[k].l].ma, node[node[k].r].ma));
}

void split(int k, int id, int& l, int& r) {
  if (k == 0) {
    l = r = 0;
    return;
  }
  if (node[node[k].l].size >= id) {
    split(node[k].l, id, l, node[k].l);
    r = k;
  } else if (node[node[k].l].size + 1 < id) {
    split(node[k].r, id - node[node[k].l].size - 1, node[k].r, r);
    l = k;
  } else {
    l = node[k].l;
    r = k;
    node[k].l = 0;
  }
  update(k);
}

int join(int x, int y) {
  if (x == 0) {
    return y;
  } else if (y == 0) {
    return x;
  } else {
    if (rand() % 1000 < 500) {
      node[x].r = join(node[x].r, y);
      update(x);
      return x;
    } else {
      node[y].l = join(x, node[y].l);
      update(y);
      return y;
    }
  }
}

bool done;
void dfs(int k) {
  if (node[k].l) {
    dfs(node[k].l);
  }
  if (done) {
    putchar(' ');
  } else {
    done = true;
  }
  printf("%d", k);
  if (node[k].r) {
    dfs(node[k].r);
  }
}

int main() {
  int n, root = 0;
  int id, x;
  int l, r;
  node[0].ma = node[0].val = -oo;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &id, &x);
    x = max(i - x, find(root, id) + 1);
    split(root, x, l, r);
    node[i].val = id;
    update(i);
    l = join(l, i);
    root = join(l, r);
  }
  done = false;
  dfs(root);
  puts("");
  return 0;
}