UVa 13102 - Tobby Stones

contents

  1. 1. Problem
  2. 2. Sample Output
  3. 3. Solution

Problem

$N$ 個石頭排成一列,一開始都是白色石頭,經過 $M$ 詢問,分別統計區間內的黑色、白色石頭個數。

操作分別有以下幾種:

1. 統計區間 [l, r] 的黑色、白色石頭個數。
2. 將區間 [l, r] 的石頭的排列反轉。
3. 將區間 [l, r] 的石頭的顏色反轉。
4. 將區間 [l, r] 的石頭的顏色全部改成 $c$

## Sample Input ##

1
2
3
4
5
6
7
8
9
10
10  7
0 0 9
3 0 4 0
0 0 4
1 0 9
0 5 9
2 5 9
0 3 9
100 1
0 0 50

Sample Output

1
2
3
4
5
0 10
5 0
5 0
0 7
0 51

Solution

用 Splay Tree 完成區間反轉,打個懶標記就可以完成,每個操作都可以在 $\mathcal{O}(\log N)$ 完成,說不定這一題用塊狀鏈表還比較容易處理,再加上快取效果還會快上很多。

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

class SPLAY_TREE { // Splay Tree
public:
static const int MAXN = 1048576;
struct Node {
static Node *EMPTY;
Node *ch[2], *fa;
char rev, set, inv, val;
int size;
int sumw, sumb;
Node() {
ch[0] = ch[1] = fa = NULL;
rev = set = inv = 0;
val = sumw = sumb = 0, size = 1;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void pushdown() {
if (rev) {
if (ch[0] != EMPTY) ch[0]->rev ^= 1;
if (ch[1] != EMPTY) ch[1]->rev ^= 1;
swap(ch[0], ch[1]);
rev ^= 1;
}
if (set) {
if (ch[0] != EMPTY) ch[0]->set = set, ch[0]->inv = 0;
if (ch[1] != EMPTY) ch[1]->set = set, ch[1]->inv = 0;
if (set == 1) // white
val = 0, sumw = sumw + sumb, sumb = 0;
else
val = 1, sumb = sumw + sumb, sumw = 0;
set = 0, inv = 0;
}
if (inv) {
if (ch[0] != EMPTY) {
if (ch[0]->set)
ch[0]->set = 3 - ch[0]->set;
else
ch[0]->inv ^= 1;
}
if (ch[1] != EMPTY) {
if (ch[1]->set)
ch[1]->set = 3 - ch[1]->set;
else
ch[1]->inv ^= 1;
}
swap(sumw, sumb), val = !val;
inv = 0;
}
}
void pushup() {
if (ch[0] != EMPTY) ch[0]->pushdown();
if (ch[1] != EMPTY) ch[1]->pushdown();
sumw = sumb = 0;
if (val == 0) sumw++;
else sumb++;
sumw += ch[0]->sumw + ch[1]->sumw;
sumb += ch[0]->sumb + ch[1]->sumb;
size = 1 + ch[0]->size + ch[1]->size;
}
} _mem[MAXN];

int bufIdx;
SPLAY_TREE::Node *root;
SPLAY_TREE() {
Node::EMPTY = &_mem[0];
Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
Node::EMPTY->size = Node::EMPTY->val = 0;
bufIdx = 1;
}
void init() {
bufIdx = 1;
}
Node* newNode() {
Node *u = &_mem[bufIdx++];
*u = Node();
u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
y->pushup();
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
x->pushdown();
}
Node* find_rt(Node *x) {
for (; x->fa != Node::EMPTY; x = x->fa);
return x;
}
void splay(Node *x, Node *below) {
Node *y, *z;
deal(x);
while (!x->is_root() && x->fa != below) {
y = x->fa, z = y->fa;
if (!y->is_root() && y->fa != below) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
x->pushup();
if (x->fa == Node::EMPTY) root = x;
}
Node* build(int l, int r, Node *p, char s[]) {
if (l > r) return Node::EMPTY;
int mid = (l + r)/2;
Node *t = newNode();
t->val = s[mid], t->fa = p;
if (t->val == 0) t->sumw ++;
else t->sumb ++;
t->ch[0] = build(l, mid-1, t, s);
t->ch[1] = build(mid+1, r, t, s);
t->pushup();
if (p == Node::EMPTY) root = t;
return t;
}
void debug(Node *u){
if (u == Node::EMPTY) return;
u->pushdown();
debug(u->ch[0]);
printf("%d", u->val);
debug(u->ch[1]);
}
Node* kthNode(int pos) {
Node *u = root;
for (int t; u != Node::EMPTY;) {
u->pushdown();
t = u->ch[0]->size;
if (t+1 == pos) return u;
if (t >= pos)
u = u->ch[0];
else
pos -= t+1, u = u->ch[1];
}
return Node::EMPTY;
}
void insert(int pos, int val) {
Node *p, *q, *r;
p = kthNode(pos), q = kthNode(pos+1);
r = newNode();
splay(p, Node::EMPTY);
splay(q, root);
r->val = val, q->ch[0] = r, r->fa = q;
splay(r, Node::EMPTY);
}
void erase(int pos) {
Node *p, *q;
p = kthNode(pos-1), q = kthNode(pos+1);
splay(p, Node::EMPTY), splay(q, root);
q->ch[0] = Node::EMPTY;
splay(q, Node::EMPTY);
}
void reverse(int l, int r) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
q->ch[0]->rev ^= 1;
splay(q->ch[0], Node::EMPTY);
}
void inverse(int l, int r) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
q->ch[0]->inv ^= 1;
splay(q->ch[0], Node::EMPTY);
}
void reset(int l, int r, int c) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
if (c == 1) {
q->ch[0]->set = 1;
} else {
q->ch[0]->set = 2;
}
splay(q->ch[0], Node::EMPTY);
}
pair<int, int> stat(int l, int r) {
Node *p, *q;
p = kthNode(l), q = kthNode(r+2);
splay(p, Node::EMPTY), splay(q, root);
return make_pair(q->ch[0]->sumb, q->ch[0]->sumw);
}

} tree;
SPLAY_TREE::Node *SPLAY_TREE::Node::EMPTY;

int main() {
static char s[1048576] = {}; // white
int n, m, cmd, l, r, c;
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 0; i <= n+1; i++)
s[i] = 0;
tree.init();
tree.build(0, n+1, SPLAY_TREE::Node::EMPTY, s);
pair<int, int> ret;
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 0) {
scanf("%d %d", &l, &r);
ret = tree.stat(l+1, r+1);
printf("%d %d\n", ret.first, ret.second);
} else if (cmd == 1) {
scanf("%d %d", &l, &r);
tree.reverse(l+1, r+1);
} else if (cmd == 2) {
scanf("%d %d", &l, &r);
tree.inverse(l+1, r+1);
} else if (cmd == 3) {
scanf("%d %d %d", &l, &r, &c);
tree.reset(l+1, r+1, c);
}
}
}
return 0;
}