伸展树专题 | guanghechen

题目
¶

hihoCoder/1329
¶

基础题。

hihocoder-1329.cpp | 166 lines.

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
#include <bits/stdc++.h>

typedef long long LL;

struct node {
  int key;
  int siz;
  node* lson;
  node* rson;

  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};

typedef node* root;
typedef std::pair<node*, node*> droot;
const int MAX_NODES = 200000 + 10;

node* null;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key = 0) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->lson = null;
  nodetop->rson = null;
  return nodetop++;
}

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}
inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}
inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = null;
  o->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->rson = right;
  left->maintain();
  return left;
}

inline int rank(root o, int key) {
  if (o == null) return 0;
  if (key == o->key) return o->lson->siz;
  if (key < o->key) return rank(o->lson, key);
  return o->lson->siz + 1 + rank(o->rson, key);
}

inline void insert(root& o, int id) {
  int k = rank(o, id);
  root left, right;
  root middle = newnode(id);
  split(o, k, left, right);
  o = merge(merge(left, middle), right);
}

inline void remove(root& o, int id1, int id2) {
  int k1 = rank(o, id1);
  int k2 = rank(o, id2 + 1);
  if (k1 >= k2) return;

  root left, middle, right;
  split(o, k1, left, right);
  split(right, k2 - k1, middle, right);
  o = merge(left, right);
}

inline int query(root& o, int key) {
  if (o == null) return 0;
  if (key < o->key) return query(o->lson, key);
  return std::max(o->key, query(o->rson, key));
}

root rt;
void Init() {
  null = new node();
  null->key = 0;
  null->siz = 0;
  null->lson = NULL;
  null->rson = NULL;

  nodetop = nodepool;
  rt = newnode(0);
  rt->rson = newnode(1000000001);
}

int N, arg1, arg2, arg3;
char cmd[20];
inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  Init();
  N = read();
  for (int i = 1; i <= N; ++i) {
    scanf("%s", cmd);
    arg1 = std::min(std::max(read(), 1), 1000000000);
    if (cmd[0] == 'D') arg2 = std::min(std::max(read(), 1), 1000000000);

    switch (cmd[0]) {
    case 'I':
      insert(rt, arg1);
      break;
    case 'Q':
      printf("%lld\n", query(rt, arg1));
      break;
    case 'D':
      remove(rt, arg1, arg2);
      break;
    }
  }
  return 0;
}

hihoCoder/1333
¶

题目链接： hihoCoder/1333 平衡树 Splay2

节点中维护 add，sum，key，siz，val；其中

key 为每个人的 id
val 为每个人的兴趣值

在进行区间操作时，利用 key，计算出左右区间在 Splay 中的名次，然后使用该名次加上基础 Splay 操作就可以了。

hihocoder-1333.cpp | 213 lines.

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

typedef long long LL;

struct node {
  int key;
  int siz;
  int val;
  int add;
  LL sum;
  node* lson;
  node* rson;

  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void pushdown() {
    if (!add) return;
    lson->update(add);
    rson->update(add);
    add = 0;
  }
  void update(int add) {
    if (this->lson == NULL) return;
    this->add += add;
    this->val += add;
    this->sum += (LL)add * this->siz;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
    sum = lson->sum + val + rson->sum;
  }
};

typedef node* root;
typedef std::pair<node*, node*> droot;
const int MAX_NODES = 200000 + 10;

node* null;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key = 0, int val = 0) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->val = val;
  nodetop->add = 0;
  nodetop->sum = val;
  nodetop->lson = null;
  nodetop->rson = null;
  return nodetop++;
}

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}
inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}
inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    p->pushdown();
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = null;
  o->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->rson = right;
  left->maintain();
  return left;
}

inline int rank(root o, int key) {
  if (o == null) return 0;
  if (key == o->key) return o->lson->siz;
  if (key < o->key) return rank(o->lson, key);
  return o->lson->siz + 1 + rank(o->rson, key);
}

inline void insert(root& o, int id, int val) {
  int k = rank(o, id);
  root left, right;
  root middle = newnode(id, val);
  split(o, k, left, right);
  o = merge(merge(left, middle), right);
}

inline void remove(root& o, int id1, int id2) {
  int k1 = rank(o, id1);
  int k2 = rank(o, id2 + 1);
  if (k1 >= k2) return;

  root left, middle, right;
  split(o, k1, left, right);
  split(right, k2 - k1, middle, right);
  o = merge(left, right);
}

inline void update(root& o, int id1, int id2, int add) {
  int k1 = rank(o, id1);
  int k2 = rank(o, id2 + 1);
  if (k1 >= k2) return;

  splay(o, k1);
  splay(o->rson, k2 - k1 + 1);
  o->rson->lson->update(add);
  o->rson->maintain();
  o->maintain();
}

inline LL query(root& o, int id1, int id2) {
  int k1 = rank(o, id1);
  int k2 = rank(o, id2 + 1);
  if (k1 >= k2) return 0;

  splay(o, k1);
  splay(o->rson, k2 - k1 + 1);
  return o->rson->lson->sum;
}

root rt;
void Init() {
  null = new node();
  null->key = 0;
  null->siz = 0;
  null->val = 0;
  null->add = 0;
  null->sum = 0;
  null->lson = NULL;
  null->rson = NULL;

  nodetop = nodepool;
  rt = newnode(0, 0);
  rt->rson = newnode(1000000001, 0);
}

int N, arg1, arg2, arg3;
char cmd[20];
inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  Init();
  N = read();
  for (int i = 1; i <= N; ++i) {
    scanf("%s", cmd);
    arg1 = std::min(std::max(read(), 1), 100000000);
    arg2 = std::min(std::max(read(), 1), 100000000);
    if (cmd[0] == 'M') arg3 = read();

    switch (cmd[0]) {
    case 'I':
      insert(rt, arg1, arg2);
      break;
    case 'Q':
      printf("%lld\n", query(rt, arg1, arg2));
      break;
    case 'M':
      update(rt, arg1, arg2, arg3);
      break;
    case 'D':
      remove(rt, arg1, arg2);
      break;
    }
  }
  return 0;
}

法二：将原序列离散化到 $1 \sim N$ ，并建成 Splay，多维护一个区间最小值，利用维护的 siz，就可以实现名次树的一些功能，就可以快速查找了。

LA-3961_2.cpp | 173 lines.

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>

struct node {
  int key;
  int siz;
  int minv;
  bool flip;
  node* lson;
  node* rson;

  int cmp(int key) {
    int cnt = lson->siz + 1;
    if (key == cnt) return -1;
    return key < cnt ? 0 : 1;
  }
  void reverse() {
    flip ^= 1;
    std::swap(lson, rson);
  }
  void pushdown() {
    if (!flip) return;
    lson->reverse();
    rson->reverse();
    flip = false;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
    minv = std::min(key, std::min(lson->minv, rson->minv));
  }
};

typedef node* root;
node* null;

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}
inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}
inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    p->pushdown();
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d2 ^ 1);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = null;
  o->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->rson = right;
  left->maintain();
  return left;
}

inline int kth(root rt) {
  rt->pushdown();
  if (rt->key == rt->minv) return rt->lson->siz + 1;
  if (rt->lson->minv < rt->rson->minv) return kth(rt->lson);
  return kth(rt->rson) + rt->lson->siz + 1;
}

const int MAX_NODES = 100000 + 10;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key = 0) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->minv = key;
  nodetop->flip = false;
  nodetop->lson = null;
  nodetop->rson = null;
  return nodetop++;
}

inline void build(root& o, int lft, int rht, int* rank) {
  int mid = (lft + rht) >> 1;
  o = newnode(rank[mid]);
  if (lft < mid) build(o->lson, lft, mid - 1, rank);
  if (mid < rht) build(o->rson, mid + 1, rht, rank);
  o->maintain();
}

const int MAXN = 100000 + 10;
const int INF = 0x3f3f3f3f;
int N, A[MAXN], id[MAXN], rank[MAXN];
root rt;

inline bool cmp(int u, int v) {
  return A[u] < A[v];
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

inline void init() {
  nodetop = nodepool;
}

inline int solve() {
  int k = kth(rt);
  splay(rt, k);
  int ans = rt->lson->siz;
  if (ans) {
    rt->lson->reverse();
    splay(rt->lson, rt->lson->siz);
    rt = merge(rt->lson, rt->rson);
  } else
    rt = rt->rson, rt->pushdown();
  return ans;
}

int main() {
  null = new node();
  null->key = 0;
  null->siz = 0;
  null->minv = INF;
  null->flip = false;
  null->lson = NULL;
  null->rson = NULL;

  while (scanf("%d", &N) == 1 && N) {
    init();
    for (int i = 1; i <= N; ++i) A[i] = read();
    for (int i = 1; i <= N; ++i) id[i] = i;
    std::stable_sort(id + 1, id + N + 1, cmp);
    for (int i = 1; i <= N; ++i) rank[id[i]] = i;
    build(rt, 1, N, rank);
    for (int i = 1; i < N; ++i) printf("%d ", solve() + i);
    printf("%d\n", N);
  }
  return 0;
}

Update time: 2016/07/06

HYSBZ/1269
¶

题目链接： HYSBZ/1269 文本编辑器 editor

都是一些 Splay 的经典操作，为了方便操作，在最最左边和最右边分别加了一个虚拟节点。

hysbz-1269.cpp | 201 lines.

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <bits/stdc++.h>

struct node {
  char key;
  int siz;
  bool flip;
  node* lson;
  node* rson;

  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void reverse() {
    flip ^= 1;
    std::swap(lson, rson);
  }
  void pushdown() {
    if (!flip) return;
    lson->reverse();
    rson->reverse();
    flip ^= 1;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};

typedef node* root;
const int MAX_NODES = (1 << 22) + 10;
node* null;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(char key) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->flip = false;
  nodetop->lson = null;
  nodetop->rson = null;
  return nodetop++;
}

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}
inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}
inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    p->pushdown();
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = null;
  o->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->rson = right;
  left->maintain();
  return left;
}

inline void build(root& o, int lft, int rht, char* s) {
  int mid = (lft + rht) >> 1;
  o = newnode(s[mid]);
  if (lft < mid) build(o->lson, lft, mid - 1, s);
  if (mid < rht) build(o->rson, mid + 1, rht, s);
  o->maintain();
}

const int MAXN = (1 << 22) + 10;
char s[MAXN];

inline void Move(root& rt, int k) {
  splay(rt, k);
}
inline void Insert(root& rt, int n) {
  for (s[1] = getchar(); s[1] < 32 || s[1] > 126;) s[1] = getchar();
  for (int i = 2; i <= n; ++i) s[i] = getchar();
  root left = rt;
  root middle;
  build(middle, 1, n, s);
  root right = rt->rson;
  rt->rson = null;
  rt->maintain();
  rt = merge(left, merge(middle, right));
}
inline void Delete(root& rt, int n) {
  splay(rt->rson, n);
  rt->rson = rt->rson->rson;
  rt->maintain();
}
inline void Rotate(root& rt, int n) {
  splay(rt->rson, n + 1);
  rt->rson->lson->reverse();
}
inline void Get(root& rt) {
  root o = rt->rson;
  for (; o->lson != null; o = o->lson) o->pushdown();
  printf("%c\n", o->key);
}
inline void Prev(root& rt) {
  splay(rt, rt->lson->siz);
}
inline void Next(root& rt) {
  splay(rt, rt->lson->siz + 2);
}

root rt;
inline void Init() {
  null = new node();
  null->key = '\0';
  null->siz = 0;
  null->flip = false;
  null->lson = NULL;
  null->rson = NULL;

  nodetop = nodepool;
  rt = newnode(31);
  rt->rson = newnode(127);
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return s;
}

char cmd[20];

int main() {
  Init();

  int N = read();
  for (int i = 1; i <= N; ++i) {
    scanf("%s", cmd);
    switch (cmd[0]) {
    case 'M':
      Move(rt, read() + 1);
      break;
    case 'I':
      Insert(rt, read());
      break;
    case 'D':
      Delete(rt, read());
      break;
    case 'R':
      Rotate(rt, read());
      break;
    case 'G':
      Get(rt);
      break;
    case 'P':
      Prev(rt);
      break;
    case 'N':
      Next(rt);
      break;
    }
  }
  return 0;
}

Update time: 2016/07/05

HYSBZ/1500
¶

题目链接： HYSBZ/1500 维修数列

前五个操作比较简单，第六个操作，需要维护：

子树左侧起最大连续和 $m x l v$ （可以为空）
子树右侧起最大连续和 $m x r v$ （可以为空）
子树中最大连续和 $m x m v$ （非空）。

在序列的最左侧和最右侧增加两个虚拟节点就可以很方便了，注意为了不影响结果的正确性，虚拟节点的 sum 值需为 $0$ ，但是节点的 $k e y, m x l v, m x m v, m x r v$ 均需设成负无穷。

hysbz-1500.cpp | 278 lines.

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f;

struct node {
  int key;
  int siz;
  int setv;   // 懒惰标记，表示是否标记为同一个值
  int sumv;   // 该节点为根的子树的 $\sum key$
  int mxlv;   // 该节点为根的子树表示的序列左侧（可以为空）最大连续和
  int mxmv;   // 该节点为根的子树最大连续和
  int mxrv;   // 该节点为根的子树表示的序列右侧（可以为空）最大连续和
  bool flip;   // 懒惰标记，表示是否翻转
  node* lson;
  node* rson;

  static node* null;

  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void reverse() {
    flip ^= 1;
    std::swap(lson, rson);
    std::swap(mxlv, mxrv);
  }
  void update(int tag) {
    setv = tag;
    key = tag;
    sumv = tag * siz;
    mxlv = mxrv = tag > 0 ? sumv : 0;
    mxmv = tag > 0 ? sumv : tag;
  }
  void pushdown() {
    if (flip) {
      lson->reverse();
      rson->reverse();
      flip = false;
    }
    if (setv != -INF) {
      if (lson != null) lson->update(setv);
      if (rson != null) rson->update(setv);
      setv = -INF;
    }
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
    sumv = lson->sumv + key + rson->sumv;
    mxlv = std::max(lson->mxlv, lson->sumv + key + rson->mxlv);
    mxrv = std::max(rson->mxrv, lson->mxrv + key + rson->sumv);
    mxmv = std::max(lson->mxmv, rson->mxmv);
    mxmv = std::max(mxmv, lson->mxrv + key + rson->mxlv);
  }
};

typedef node* root;
node* node::null = new node();

inline void printtree(root o, int cur = 0) {
  if (o == node::null) return;
  o->pushdown();
  o->maintain();
  printtree(o->lson, cur + 1);
  printf("cur %d: key=%d, siz=%d, sum=%d\n", cur, o->key, o->siz, o->sumv);
  printtree(o->rson, cur + 1);
  if (!cur) printf("-------------------------------------\n");
}

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}

inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}

inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    p->pushdown();
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = node::null;
  o->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->rson = right;
  left->maintain();
  return left;
}

/********************** 以上为 splay 基本操作 *******************/

const int MAX_NODES = 1000000 + 10;
std::queue<root> Qnodepool;
node nodepool[MAX_NODES];

inline root newnode(int key = 0) {
  root nodetop = Qnodepool.front();
  Qnodepool.pop();
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->setv = -INF;
  nodetop->sumv = key;
  nodetop->mxlv = key > 0 ? key : 0;
  nodetop->mxmv = key;
  nodetop->mxrv = key > 0 ? key : 0;
  nodetop->flip = false;
  nodetop->lson = node::null;
  nodetop->rson = node::null;
  return nodetop;
}

inline void deletenode(root o) {
  if (o == node::null) return;
  deletenode(o->lson);
  deletenode(o->rson);
  Qnodepool.push(o);
}

inline void build(root& o, int lft, int rht, int* A) {
  int mid = (lft + rht) >> 1;
  o = newnode(A[mid]);
  if (lft < mid) build(o->lson, lft, mid - 1, A);
  if (mid < rht) build(o->rson, mid + 1, rht, A);
  if (A[mid] == -INF) o->sumv = 0;
  o->maintain();
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

const int MAXN = 500000 + 10;
int A[MAXN];
root rt;

inline void INSERT(int pos, int tot) {
  for (int i = 1; i <= tot; ++i) A[i] = read();
  root left, middle, right;
  build(middle, 1, tot, A);
  split(rt, pos + 1, left, right);
  rt = merge(merge(left, middle), right);
}

inline void DELETE(int pos, int tot) {
  splay(rt, pos);
  splay(rt->rson, tot + 1);

  deletenode(rt->rson->lson);

  rt->rson->lson = node::null;
  rt->rson->maintain();
  rt->maintain();
}

inline void MODIFY(int pos, int tot, int tag) {
  splay(rt, pos);
  splay(rt->rson, tot + 1);
  rt->rson->lson->update(tag);
  rt->rson->maintain();
  rt->maintain();
}

inline void REVERSE(int pos, int tot) {
  splay(rt, pos);
  splay(rt->rson, tot + 1);
  rt->rson->lson->reverse();
  rt->rson->maintain();
  rt->maintain();
}

inline int GETSUM(int pos, int tot) {
  splay(rt, pos);
  splay(rt->rson, tot + 1);
  return rt->rson->lson->sumv;
}

inline int MAXSUM() {
  return rt->mxmv;
}

inline void init() {
  while (!Qnodepool.empty()) Qnodepool.pop();
  for (int i = 0; i < MAX_NODES; ++i) Qnodepool.push(nodepool + i);
  node::null->key = -INF;
  node::null->siz = 0;
  node::null->setv = -INF;
  node::null->sumv = 0;
  node::null->mxlv = 0;
  node::null->mxmv = -INF;
  node::null->mxrv = 0;
  node::null->flip = false;
  node::null->lson = NULL;
  node::null->rson = NULL;
}

int main() {
  init();

  int N = read();
  int Q = read();

  for (int i = 1; i <= N; ++i) A[i] = read();
  A[0] = A[N + 1] = -INF;
  build(rt, 0, N + 1, A);
  while (Q--) {
    char cmd[20];
    scanf("%s", cmd);
    if (cmd[0] == 'M' && cmd[2] == 'X') {
      printf("%d\n", MAXSUM());
      continue;
    }

    int arg1 = read();
    int arg2 = read();

    switch (cmd[0]) {
    case 'I':
      INSERT(arg1, arg2);
      break;
    case 'D':
      DELETE(arg1, arg2);
      break;
    case 'M':
      MODIFY(arg1, arg2, read());
      break;
    case 'R':
      REVERSE(arg1, arg2);
      break;
    case 'G':
      printf("%d\n", GETSUM(arg1, arg2));
      break;
    }
  }

  return 0;
}

update time: 2016/07/07

HYSBZ/1503
¶

题目链接： HYSBZ/1503 郁闷的出纳员

只需要用 Splay 实现名次树即可。注意由于存在懒惰标记，在查询第 $k$ 大，及确定有多少个值比 $k e y$ 小，这两个操作的过程中都要一路 $p u s h d o w n$ 。

HINT

坑点：立即离开公司的人不算入答案。。。

hysbz-1503.cpp | 198 lines.

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <bits/stdc++.h>

struct node {
  int key;
  int siz;
  int addv;
  node* lson;
  node* rson;

  static node* null;

  int cmp(int s) {
    int cnt = lson->siz + 1;
    if (s == cnt) return -1;
    return s < cnt ? 0 : 1;
  }
  void update(int v) {
    key += v;
    addv += v;
  }
  void pushdown() {
    if (!addv) return;
    if (lson != null) lson->update(addv);
    if (rson != null) rson->update(addv);
    addv = 0;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};

typedef node* root;

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}

inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}

inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void printtree(root o, int cur = 0) {
  if (o == node::null) return;
  printtree(o->lson, cur + 1);
  printf("cur %d: key=%d, siz=%d\n", cur, o->key, o->siz);
  printtree(o->rson, cur + 1);
  if (!cur) printf("---------------------------------\n");
}

inline void splay(root& o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    p->pushdown();
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline int kth(root o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == -1) return o->key;
  return d ? kth(o->rson, k - o->lson->siz - 1) : kth(o->lson, k);
}

inline int rank(root o, int k) {
  if (o == node::null) return 0;
  o->pushdown();
  if (k <= o->key) return rank(o->lson, k);
  return rank(o->rson, k) + o->lson->siz + 1;
}

const int MAX_NODES = 100000 + 10;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key = 0) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->addv = 0;
  nodetop->lson = node::null;
  nodetop->rson = node::null;
  return nodetop++;
}

inline void insert(root& rt, int key) {
  int k = rank(rt, key);
  splay(rt, k);
  root left = rt;
  root middle = newnode(key);
  root right = rt->rson;
  left->rson = middle;
  middle->rson = right;
  middle->maintain();
  left->maintain();
  rt = left;
}

inline void remove(root& rt, int M) {
  int k = rank(rt, M);
  if (k == 1) return;
  splay(rt, 1);
  splay(rt->rson, k);
  rt->rson->lson = node::null;
  rt->rson->maintain();
  rt->maintain();
}

inline void update(root& rt, int addv) {
  if (rt->siz == 2) return;
  splay(rt, 1);
  splay(rt->rson, rt->rson->siz);
  rt->rson->lson->update(addv);
  rt->rson->maintain();
  rt->maintain();
}

const int INF = 0x3f3f3f3f;
root rt;

node* node::null = new node();
inline void init() {
  node::null->key = 0;
  node::null->siz = 0;
  node::null->addv = 0;
  node::null->lson = NULL;
  node::null->rson = NULL;

  nodetop = nodepool;
  rt = newnode(-INF);
  rt->rson = newnode(INF);
  rt->maintain();
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  init();

  int N = read();
  int M = read();
  int tot = 2;
  for (int i = 1; i <= N; ++i) {
    char cmd[20];
    scanf("%s", cmd);
    int arg = read();

    switch (cmd[0]) {
    case 'I':
      if (arg >= M) insert(rt, arg), ++tot;
      break;
    case 'A':
      update(rt, arg);
      break;
    case 'S':
      update(rt, -arg);
      remove(rt, M);
      break;
    case 'F':
      printf("%d\n", arg <= rt->siz - 2 ? kth(rt, rt->siz - arg) : -1);
      break;
    }
  }
  printf("%d\n", tot - rt->siz);

  return 0;
}

Update time: 2016/07/07

LA/3961
¶

题目链接： LA/3961 Robotic Sort

初始时，建一棵 $1 \sim N$ 的 Splay，并对原序列进行排序（排序规则为：值小的优先，值相等时，在原序列靠左的优先）。对于第 $k$ 次询问，将值为 $k$ 的节点伸展至根，然后就是些基础的操作了。问题的难点在于快速找到值为 $k$ 的节点。

法一：用一个父指针，直接从值为 $k$ 的节点往上伸展就好了。之所以扯这么多，是因为此前一直都是用刘汝佳的递归写法（被惯坏了），不需要父指针。

LA-3961.cpp | 164 lines.

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
#include <bits/stdc++.h>

struct node {
  int key;
  int siz;
  bool flip;
  node* prev;
  node* lson;
  node* rson;

  void reverse() {
    flip ^= 1;
    std::swap(lson, rson);
  }
  void pushdown() {
    if (!flip) return;
    lson->reverse();
    rson->reverse();
    flip = false;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};

typedef node* root;

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson->prev = o;
  k->lson = o;
  o->prev = k;
  o = k;
}
inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson->prev = o;
  k->rson = o;
  o->prev = k;
  o = k;
}
// 带父指针的 旋转 和 伸展操作 是此问题最大的难点（蒽，被刘汝佳的代码惯坏了。。
inline void rotate(root o, int d) {
  int d2 = -1;
  root p = o->prev;
  if (p != NULL) d2 = p->lson == o ? 0 : 1;
  d ? zig(o) : zag(o);
  if (d2 != -1) d2 ? p->rson = o : p->lson = o;
  d ? o->rson->maintain() : o->lson->maintain();
  o->prev = p;
  o->maintain();
}

// 注意，d 必须在 pushdown 之后计算，因为有交换子树的操作。
inline void splay(root o, root f) {
  // o 必须先 pushdown() 一次，因为可能 o 已经是 f 的子节点，
  // 但为了保持 “splay 操作后的根节点标记全部下传” 的传统，需要这么做。
  for (o->pushdown(); o->prev != f;) {
    root p = o->prev;
    if (p->prev == f) {
      p->pushdown();
      o->pushdown();
      int d = p->lson == o ? 0 : 1;
      rotate(p, d ^ 1);
      break;
    }

    root g = p->prev;
    g->pushdown();
    p->pushdown();
    o->pushdown();
    int d = p->lson == o ? 0 : 1;
    int d2 = g->lson == p ? 0 : 1;
    if (d == d2)
      rotate(g, d2 ^ 1), rotate(p, d ^ 1);
    else
      rotate(p, d ^ 1), rotate(g, d2 ^ 1);
  }
}

const int MAX_NODES = 100000 + 10;
node* null;
node nodepool[MAX_NODES];

inline void build(root& o, int lft, int rht) {
  int mid = (lft + rht) >> 1;
  o = nodepool + mid;
  o->key = mid;
  o->siz = 1;
  o->flip = false;
  if (lft < mid)
    build(o->lson, lft, mid - 1);
  else
    o->lson = null;
  if (mid < rht)
    build(o->rson, mid + 1, rht);
  else
    o->rson = null;
  o->lson->prev = o;
  o->rson->prev = o;
  o->maintain();
}

inline int solve(root& rt, int key) {
  root o = nodepool + key;
  splay(o, rt->prev);
  int ans = o->lson->siz;
  if (ans) {
    root k = o->lson;
    k->reverse();
    for (; k->rson != null; k = k->rson) k->pushdown();
    splay(k, o);
    k->rson = o->rson;
    o->rson->prev = k;
    o = k;
  } else
    o = o->rson;
  rt = o;
  rt->prev = NULL;
  rt->maintain();
  return ans;
}

typedef std::pair<int, int> pii;
const int MAXN = 100000 + 10;

root rt;
pii A[MAXN];
int N;

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = true;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

inline void Init() {
  for (int i = 1; i <= N; ++i) A[i] = pii(read(), i);
  sort(A + 1, A + N + 1);
  build(rt, 1, N);
  rt->prev = NULL;
}

int main() {
  null = new node();
  null->key = 0;
  null->siz = 0;
  null->flip = false;
  null->lson = NULL;
  null->rson = NULL;

  while (scanf("%d", &N) == 1 && N) {
    Init();
    for (int i = 1; i < N; ++i) printf("%d ", solve(rt, A[i].second) + i);
    printf("%d\n", N);
  }
  return 0;
}

Update time: 2016/07/05

POJ/2828
¶

题目链接： POJ/2828 Buy Tickets

法一：在线做。直接 Splay 模拟，容易超时，可以检验自己 Splay 写法常数大不大（不加读入读出优化的前提下）。

HINT

POJ 加读入读出优化能快很多 = =

poj-2828.cpp | 144 lines.

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

struct node {
  int key;
  int siz;
  node* lson;
  node* rson;

  static node* null;

  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};

typedef node* root;

inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}

inline void zig(root& o) {
  root k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}

inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = node::null;
  o->maintain();
}

const int MAX_NODES = 200000 + 10;

node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key = 0) {
  nodetop->key = key;
  nodetop->siz = 0;
  nodetop->lson = node::null;
  nodetop->rson = node::null;
  return nodetop++;
}

inline void insert(root& rt, int pos, int key) {
  root left, right;
  split(rt, pos + 1, left, right);
  left->rson = newnode(key);
  left->rson->rson = right;
  left->rson->maintain();
  left->maintain();
  rt = left;
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

inline void print(int s) {
  if (s > 9) print(s / 10);
  putchar(s % 10 + '0');
}

node* node::null = new node();
root rt;
int N;

inline void init() {
  node::null->key = 0;
  node::null->siz = 0;
  node::null->lson = NULL;
  node::null->rson = NULL;
}

inline void printtree(root& o) {
  if (o == node::null) return;
  printtree(o->lson);
  print(o->key);
  putchar(' ');
  printtree(o->rson);
}

int main() {
  init();
  while (scanf("%d", &N) == 1) {
    nodetop = nodepool;
    rt = newnode(0);
    for (int i = 1; i <= N; ++i) {
      int arg1 = read();
      int arg2 = read();
      insert(rt, arg1, arg2);
    }
    splay(rt, 1);
    printtree(rt->rson);
    printf("\n");
  }
  return 0;
}

法二：离线做。类似约瑟夫问题的线段树写法。初始时，维护一个前缀和 $s u m (N) = \sum_{i = 1}^{N} i$ ；最后一个人的最终位置显然是 $p o s + 1$ ，然后去掉这个人，那么倒数第二个人就成了最后一个人了。

poj-2828_2.cpp | 59 lines.

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define lc (o << 1)
#define rc (o << 1 | 1)
#define lson lc, lft, mid
#define rson rc, mid + 1, rht
#define MID(lft, rht) (lft + rht >> 1)

const int MAXN = 200000 + 10;

int sumv[MAXN << 2], ans[MAXN], pos[MAXN], val[MAXN], N;
void build(int o, int lft, int rht) {
  sumv[o] = rht - lft + 1;
  if (lft == rht) return;
  int mid = MID(lft, rht);
  build(lson);
  build(rson);
}

void query(int o, int lft, int rht, int pos, int val) {
  --sumv[o];
  if (lft == rht)
    ans[lft] = val;
  else {
    int mid = MID(lft, rht);
    if (pos <= sumv[lc])
      query(lson, pos, val);
    else
      query(rson, pos - sumv[lc], val);
  }
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

inline void print(int s) {
  if (s > 9) print(s / 10);
  putchar(s % 10 + '0');
}

int main() {
  while (scanf("%d", &N) == 1) {
    build(1, 1, N);
    for (int i = 1; i <= N; ++i) pos[i] = read() + 1, val[i] = read();
    for (int i = N; i; --i) query(1, 1, N, pos[i], val[i]);
    for (int i = 1; i <= N; ++i) print(ans[i]), putchar(' ');
    putchar('\n');
  }
  return 0;
}

Update time: 2016/07/07

UVA/11922
¶

题目链接： UVA/11922 Permutation Transformer

基础题。

uva-11922.cpp | 138 lines.

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
#include <bits/stdc++.h>
using namespace std;

struct node {
  int key;
  int siz;
  bool flip;
  node* lson;
  node* rson;
  node(int key = 0) : key(key), siz(0), flip(0), lson(NULL), rson(NULL) {
  }
  int cmp(int key) {
    int cnt = lson->siz + 1;
    if (key == cnt) return -1;
    return key < cnt ? 0 : 1;
  }
  void pushdown() {
    if (!flip) return;
    lson->flip ^= 1;
    rson->flip ^= 1;
    swap(lson, rson);
    flip = false;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};

typedef node* root;
typedef pair<node*, node*> droot;
const int MAX_NODES = 100000 + 10;
node* null = new node();

node nodepool[MAX_NODES];
node* nodetop;

inline node* newnode(int key = 0) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->flip = false;
  nodetop->lson = null;
  nodetop->rson = null;
  return nodetop++;
}

inline void zag(root& o) {
  node* k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}
inline void zig(root& o) {
  node* k = o->lson;
  o->lson = k->rson;
  k->rson = o;
  o = k;
}
inline void rotate(root& o, int d) {
  d ? zig(o) : zag(o);
  d ? o->rson->maintain() : o->lson->maintain();
  o->maintain();
}

inline void splay(root& o, int k) {
  o->pushdown();
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    p->pushdown();
    int d2 = p->cmp(k);
    if (d2 == 1) k -= p->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? p->rson : p->lson), k);
      if (d == d2)
        rotate(o, d ^ 1);
      else
        rotate(p, d);
    }
    rotate(o, d ^ 1);
  }
}

inline void split(root o, int k, root& left, root& right) {
  splay(o, k);
  left = o;
  right = o->rson;
  o->rson = null;
  o->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->pushdown();
  left->rson = right;
  left->maintain();
  return left;
}

inline void build(root& o, int lft, int rht) {
  int mid = (lft + rht) >> 1;
  o = newnode(mid);
  if (lft < mid) build(o->lson, lft, mid - 1);
  if (mid < rht) build(o->rson, mid + 1, rht);
  o->maintain();
}

inline void print(root& o) {
  if (o == null) return;
  o->pushdown();
  if (o->lson != null) print(o->lson);
  if (o->key) printf("%d\n", o->key);
  if (o->rson != null) print(o->rson);
}

root rt;
inline void init(int N) {
  nodetop = nodepool;
  build(rt, 0, N);
}

int main() {
  int N, Q;
  while (scanf("%d%d", &N, &Q) == 2) {
    init(N);
    while (Q--) {
      int lft, rht;
      root o, left, middle, right;
      scanf("%d%d", &lft, &rht);
      split(rt, lft, left, o);
      split(o, rht - lft + 1, middle, right);
      middle->flip ^= 1;
      rt = merge(merge(left, right), middle);
    }
    print(rt);
  }
  return 0;
}

UVA/11996
¶

题目链接： UVA/11996 Jewel Magic

用 hash 求 LCP，则仅需用 Splay 维护 hash 值即可。考虑到用反转操作，每个节点需要维护正反两个 hash 值。

uva-11996.cpp | 214 lines.

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int MAXN = 400000 + 10;
const int hashkey = 137;

ULL xp[MAXN];

struct node {
  int key;
  int siz;
  ULL val;
  ULL reval;
  bool flip;
  node* lson;
  node* rson;

  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void reverse() {
    flip ^= 1;
    swap(lson, rson);
    swap(val, reval);
  }
  void pushdown() {
    if (!flip) return;
    lson->reverse();
    rson->reverse();
    flip = false;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
    val = lson->val + key * xp[lson->siz] + rson->val * xp[lson->siz + 1];
    reval = rson->reval + key * xp[rson->siz] + lson->reval * xp[rson->siz + 1];
  }
};

typedef node* root;
typedef pair<node*, node*> droot;
const int MAX_NODES = 400000 + 10;

node* null;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key = 0) {
  nodetop->key = key;
  nodetop->siz = 1;
  nodetop->val = 0;
  nodetop->reval = 0;
  nodetop->flip = false;
  nodetop->lson = null;
  nodetop->rson = null;
  return nodetop++;
}

inline void zag(root& rt) {
  root k = rt->rson;
  rt->rson = k->lson;
  k->lson = rt;
  rt = k;
}
inline void zig(root& rt) {
  root k = rt->lson;
  rt->lson = k->rson;
  k->rson = rt;
  rt = k;
}
inline void rotate(root& rt, int d) {
  d ? zig(rt) : zag(rt);
  d ? rt->rson->maintain() : rt->lson->maintain();
  rt->maintain();
}

inline void splay(root& rt, int k) {
  rt->pushdown();
  int d = rt->cmp(k);
  if (d == 1) k -= rt->lson->siz + 1;
  if (d != -1) {
    root& pt = d ? rt->rson : rt->lson;
    pt->pushdown();
    int d2 = pt->cmp(k);
    if (d2 == 1) k -= pt->lson->siz + 1;
    if (d2 != -1) {
      splay((d2 ? pt->rson : pt->lson), k);
      if (d == d2)
        rotate(rt, d ^ 1);
      else
        rotate(pt, d);
    }
    rotate(rt, d ^ 1);
  }
}

inline void split(root rt, int k, root& left, root& right) {
  splay(rt, k);
  left = rt;
  right = rt->rson;
  rt->rson = null;
  rt->maintain();
}

inline root merge(root left, root right) {
  splay(left, left->siz);
  left->rson = right;
  left->maintain();
  return left;
}

/* insert at (k+1)th position. */
inline void insert(root& rt, int k, int key) {
  root left, right;
  root middle = newnode(key);
  split(rt, k, left, right);
  rt = merge(merge(left, middle), right);
}

/* remove at (k+1)th position. */
inline void remove(root& rt, int k) {
  root left, middle, right;
  split(rt, k, left, right);
  split(right, 1, middle, right);
  rt = merge(left, right);
}

/* modify [lft+1, rht+1]. */
inline void update(root& rt, int lft, int rht) {
  splay(rt, lft);
  splay(rt->rson, rht - lft + 2);
  rt->rson->lson->reverse(); /* update rt->rson->lson, rt->rson, rt */
  rt->rson->maintain();
  rt->maintain();
}

inline int query(root& rt, int p1, int p2) {
  int lft = 0, rht = rt->siz - p2;
  while (lft < rht) {
    int mid = (lft + rht) >> 1;
    splay(rt, p1);
    splay(rt->rson, mid + 1);
    ULL val1 = rt->rson->lson->val;
    splay(rt, p2);
    splay(rt->rson, mid + 1);
    ULL val2 = rt->rson->lson->val;
    if (val1 == val2)
      lft = mid + 1;
    else
      rht = mid;
  }
  return lft - 1;
}

root rt;
char s[MAXN];
int N, Q, op, arg1, arg2;

inline void build(root& rt, int lft, int rht) {
  int mid = (lft + rht) >> 1;
  rt = newnode(s[mid] - '0');
  if (lft < mid) build(rt->lson, lft, mid - 1);
  if (mid < rht) build(rt->rson, mid + 1, rht);
  rt->maintain();
}

inline void Init() {
  nodetop = nodepool;
  scanf("%s", s + 1);
  s[0] = s[N + 1] = '0';
  build(rt, 0, N + 1);
}

inline int read() {
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return s;
}

int main() {
  null = new node();
  memset(null, 0, sizeof(node));
  xp[0] = 1;
  for (int i = 1; i < MAXN; ++i) xp[i] = xp[i - 1] * hashkey;

  while (scanf("%d%d", &N, &Q) == 2) {
    Init();
    while (Q--) {
      op = read();
      arg1 = read();
      if (op != 2) arg2 = read();
      switch (op) {
      case 1:
        insert(rt, arg1 + 1, arg2);
        break;
      case 2:
        remove(rt, arg1);
        break;
      case 3:
        update(rt, arg1, arg2);
        break;
      case 4:
        printf("%d\n", query(rt, arg1, arg2));
        break;
      }
    }
  }
  return 0;
}

Summary
¶

Problems	Category	solution
hihoCoder/1329	基础题	Solution, Code
hihoCoder/1333	初级题	Solution, Code
HYSBZ/1269	经典题	Solution, Code
HYSBZ/1500	经典题	Solution, Code
HYSBZ/1503	初级题	Solution, Code
LA/3961	初级题	Solution, Code, Code2
POJ/2828	基础题	Solution, Code, Code2
UVa/11922	基础题	Solution, Code
UVa/11996	初级题	Solution, Code

题目¶

hihoCoder/1329¶

hihoCoder/1333¶

HYSBZ/1269¶

HYSBZ/1500¶

HYSBZ/1503¶

LA/3961¶

POJ/2828¶

UVA/11922¶

UVA/11996¶

Summary¶