UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#151546#10. 小x的城池lzy4523516ms216640kbC++5.7kb2022-07-27 21:28:402022-07-27 21:28:44

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100002;
const int MAXM = 77;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct BinaryIndexTree {
	int n; bool a[MAXN];
	void init(int x) {
		n = x - 1;
		for (int i = 1; i <= n; i++)
			a[i] = false;
	}
	void modify(int l, int r) {
		for (int i = l; i <= n; i += i & -i)
			a[i] ^= true;
		for (int i = r; i <= n; i += i & -i)
			a[i] ^= true;
	}
	bool query(int pos) {
		bool ans = false;
		for (int i = pos; i >= 1; i -= i & -i)
			ans ^= a[i];
		return ans;
	}
} edge;
int n, m, val[MAXN];
char type[MAXN];
struct info {
	int ans, al[MAXM], am[MAXM], ar[MAXM];
	bool bl[MAXM], br[MAXM], all, arr;
};
info operator + (const info &a, const info &b) {
	info ans;
	memcpy(ans.al, a.al, sizeof(a.al));
	memcpy(ans.ar, b.ar, sizeof(b.ar));
	memset(ans.am, 0, sizeof(ans.am));
	memset(ans.bl, false, sizeof(ans.bl));
	memset(ans.br, false, sizeof(ans.br));
	ans.ans = a.ans + b.ans;
	ans.all = false;
	ans.arr = a.arr && b.arr;
	for (int i = 0; i <= 75; i++) {
		if (b.bl[i + 1]) ans.ans += a.ar[i] + a.am[i];
		else if (b.arr) ans.ar[i] += a.ar[i], ans.am[i] += a.am[i];
		else ans.al[i] += a.am[i];
		ans.ar[i] += b.am[i];
		ans.br[i] = b.br[i];
		if (a.arr) ans.bl[i] = a.bl[i] | b.bl[i];
		else ans.bl[i] = a.bl[i];
	}
	return ans;
}
info operator - (const info &a, const info &b) {
	info ans;
	memcpy(ans.al, a.al, sizeof(a.al));
	memcpy(ans.ar, b.ar, sizeof(b.ar));
	memset(ans.am, 0, sizeof(ans.am));
	memset(ans.bl, false, sizeof(ans.bl));
	memset(ans.br, false, sizeof(ans.br));
	ans.ans = a.ans + b.ans;
	ans.all = a.all && b.all;
	ans.arr = false;
	for (int i = 0; i <= 75; i++) {
		if (a.br[i + 1]) ans.ans += b.al[i] + b.am[i];
		else if (a.all) ans.al[i] += b.al[i], ans.am[i] += b.am[i];
		else ans.ar[i] += b.am[i];
		ans.al[i] += a.am[i];
		ans.bl[i] = a.bl[i];
		if (b.all) ans.br[i] = a.br[i] | b.br[i];
		else ans.br[i] = b.br[i];
	}
	return ans;
}
info unita(int val) {
	info ans;
	memset(ans.al, 0, sizeof(ans.al));
	memset(ans.ar, 0, sizeof(ans.ar));
	memset(ans.bl, 0, sizeof(ans.bl));
	memset(ans.br, 0, sizeof(ans.br));
	memset(ans.am, 0, sizeof(ans.am));
	ans.am[val]++;
	ans.ans = 0;
	ans.all = ans.arr = true;
	return ans;
}
info unitb(int val) {
	info ans;
	memset(ans.al, 0, sizeof(ans.al));
	memset(ans.ar, 0, sizeof(ans.ar));
	memset(ans.bl, 0, sizeof(ans.bl));
	memset(ans.br, 0, sizeof(ans.br));
	memset(ans.am, 0, sizeof(ans.am));
	for (int i = 0; i <= val; i++)
		ans.bl[i] = ans.br[i] = true;
	ans.ans = 0;
	ans.all = ans.arr = true;
	return ans;
}
info unit(int pos) {
	if (type[pos] == 'A') return unita(val[pos]);
	else return unitb(val[pos]);
}
struct SegmentTree {
	struct Node {
		int lc, rc, home;
		bool tag;
	} a[MAXN * 2];
	info inf[MAXN], rev[MAXN];
	int tot, root, size, n;
	void update(int root, int mid) {
		int pos = a[root].home, lc = a[root].lc, rc = a[root].rc;
		bool tmp = edge.query(mid);
		if (tmp) {
			inf[pos] = (a[lc].home ? inf[a[lc].home] : unit(mid)) - (a[rc].home ? inf[a[rc].home] : unit(mid + 1));
			rev[pos] = (a[lc].home ? rev[a[lc].home] : unit(mid)) + (a[rc].home ? rev[a[rc].home] : unit(mid + 1));
		} else {
			inf[pos] = (a[lc].home ? inf[a[lc].home] : unit(mid)) + (a[rc].home ? inf[a[rc].home] : unit(mid + 1));
			rev[pos] = (a[lc].home ? rev[a[lc].home] : unit(mid)) - (a[rc].home ? rev[a[rc].home] : unit(mid + 1));
		}
	}
	void pushdown(int root) {
		if (a[root].tag) {
			int tmp = a[root].lc;
			if (a[tmp].home) swap(inf[a[tmp].home], rev[a[tmp].home]);
			a[tmp].tag ^= true;
			tmp = a[root].rc;
			if (a[tmp].home) swap(inf[a[tmp].home], rev[a[tmp].home]);
			a[tmp].tag ^= true;
			a[root].tag = false;
		}
	}
	void build(int &root, int l, int r) {
		root = ++size;
		if (l == r) return;
		a[root].home = ++tot;
		int mid = (l + r) / 2;
		build(a[root].lc, l, mid);
		build(a[root].rc, mid + 1, r);
		update(root, mid);
	}
	void init(int x) {
		n = x;
		root = size = 0;
		build(root, 1, n);
	}
	void modify(int root, int l, int r, int pos, int d) {
		if (l == r) {
			val[l] = d;
			return;
		}
		pushdown(root);
		int mid = (l + r) / 2;
		if (mid >= pos) modify(a[root].lc, l, mid, pos, d);
		else modify(a[root].rc, mid + 1, r, pos, d);
		update(root, mid);
	}
	void modify(int pos, int val) {
		modify(root, 1, n, pos, val);
	}
	void reverse(int root, int l, int r, int ql, int qr) {
		if (l == ql && r == qr) {
			a[root].tag ^= true;
			if (a[root].home) swap(inf[a[root].home], rev[a[root].home]);
			return;
		}
		pushdown(root);
		int mid = (l + r) / 2;
		if (mid >= ql) reverse(a[root].lc, l, mid, ql, min(mid, qr));
		if (mid + 1 <= qr) reverse(a[root].rc, mid + 1, r, max(mid + 1, ql), qr);
		update(root, mid);
	}
	void reverse(int l, int r) {
		edge.modify(l, r);
		reverse(root, 1, n, l, r);
	}
} ST;
int main() {
	read(n), read(m);
	edge.init(n);
	for (int i = 1; i <= n; i++) {
		read(val[i]);
		type[i] = getchar();
		while (type[i] != 'A' && type[i] != 'B') type[i] = getchar();
	}
	ST.init(n);
	while (m--) {
		static char s[15]; int x, y;
		scanf("\n%s%d%d", s, &x, &y);
		if (s[0] == 'U') ST.modify(x, y);
		else ST.reverse(x, y);
		if (n == 1) writeln(0);
		else writeln(ST.inf[ST.a[ST.root].home].ans);
	}
	return 0;
}
源文件, 语言: C++

详细

小提示：点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1228kb

input:

7 5
0 A
32 B
10 B
27 B
25 A
30 B
10 A
UPDATE 1 1
UPDATE 6 22
UPDATE 1 50
UPDATE 6 62
UPDATE 5 67

output:

2
1
0
2
1

result:

ok 5 number(s): "2 1 0 2 1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1240kb

input:

10 20
38 A
0 B
2 A
20 A
2 B
31 A
0 B
68 A
53 A
74 B
UPDATE 7 63
UPDATE 7 0
UPDATE 7 66
UPDATE 7 7
UP...

output:

6
6
6
6
6
4
5
4
6
4
1
4
1
6
6
4
6
6
6
4

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 1432kb

input:

100 100
38 A
0 B
2 A
20 A
2 B
31 A
0 B
68 A
53 A
74 B
37 A
62 A
59 A
70 A
71 A
4 A
44 A
2 B
63 A
22 ...

output:

67
67
67
67
67
67
67
67
67
63
63
66
66
66
70
70
70
70
65
64
65
54
45
69
70
69
69
46
67
67
67
67
67
6...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 3368kb

input:

1000 500
38 A
49 A
67 A
60 A
62 A
74 A
31 A
6 A
18 A
23 A
45 A
25 A
37 A
62 A
59 A
70 A
71 A
4 A
44 ...

output:

541
629
540
750
742
701
701
737
737
745
737
701
730
701
764
764
723
463
556
635
627
755
755
452
530
...

result:

ok 500 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

10 30
38 A
49 A
72 B
2 B
74 B
65 A
74 B
0 B
54 A
2 B
REVERSE 7 9
REVERSE 1 5
REVERSE 4 7
REVERSE 6 7...

output:

4
2
2
2
0
3
3
2
2
2
2
2
1
1
2
2
1
2
1
0
1
2
2
2
2
3
3
3
2
1

result:

ok 30 numbers

Test #6:

score: 0
Accepted
time: 5ms
memory: 1656kb

input:

200 400
38 A
49 A
67 A
60 A
62 A
74 A
31 A
6 A
18 A
23 A
45 A
25 A
37 A
62 A
59 A
70 A
71 A
4 A
44 A...

output:

143
100
52
74
68
74
57
33
42
42
39
27
26
45
45
45
22
26
46
43
47
39
32
22
29
22
23
19
26
26
28
28
19...

result:

ok 400 numbers

Test #7:

score: 0
Accepted
time: 19ms
memory: 3376kb

input:

1000 1000
30 A
59 A
17 A
15 A
65 A
3 A
9 A
60 A
31 A
56 A
16 A
63 A
47 A
47 A
45 A
43 A
28 A
11 A
42...

output:

178
312
311
85
85
242
131
194
128
128
134
134
97
90
90
104
64
104
104
136
113
44
117
109
27
27
27
27...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 6ms
memory: 2096kb

input:

400 400
4 A
16 A
72 A
53 A
73 B
34 A
72 A
31 A
37 A
9 A
7 A
30 A
53 A
15 A
57 A
21 A
69 A
74 A
38 A
...

output:

186
68
129
129
72
67
75
144
97
11
4
4
12
13
17
36
32
13
17
38
15
15
39
39
15
9
17
31
16
16
31
31
24
...

result:

ok 400 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 1232kb

input:

7 4
0 A
32 B
10 B
27 B
25 A
30 B
10 A
REVERSE 2 5
UPDATE 5 30
REVERSE 5 7
UPDATE 2 0

output:

2
2
3
1

result:

ok 4 number(s): "2 2 3 1"

Test #10:

score: 0
Accepted
time: 16ms
memory: 3380kb

input:

1000 1000
65 B
28 A
3 B
48 B
19 B
35 B
19 B
12 B
1 B
29 B
18 A
5 B
38 B
16 B
23 B
19 B
22 B
2 B
31 A...

output:

133
133
121
121
121
115
115
119
115
115
113
104
106
107
109
108
103
103
103
94
94
90
90
90
90
90
90
...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 18ms
memory: 3380kb

input:

1000 1000
74 A
53 A
32 A
2 B
52 A
19 B
10 B
13 B
15 B
30 B
35 B
15 B
10 B
65 A
64 A
33 A
24 B
32 B
1...

output:

331
319
296
295
286
269
275
252
252
266
265
242
243
232
232
232
227
228
211
222
208
208
209
220
207
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 13ms
memory: 3384kb

input:

1000 1000
43 A
42 A
44 A
56 A
63 A
43 B
22 A
65 A
31 B
8 B
45 A
52 A
32 B
2 B
18 A
6 B
14 A
39 A
0 B...

output:

336
328
328
276
281
280
273
273
273
259
258
258
258
270
271
260
259
254
254
254
254
256
256
259
247
...

result:

ok 1000 numbers

Test #13:

score: 0
Accepted
time: 17ms
memory: 3380kb

input:

1000 1000
11 B
13 B
23 B
21 B
59 A
29 B
67 A
22 A
1 A
68 A
7 A
65 A
72 A
4 A
42 A
71 A
30 B
41 B
0 B...

output:

449
449
423
372
340
313
299
300
283
283
305
304
265
242
237
240
234
235
230
222
220
220
219
214
218
...

result:

ok 1000 numbers

Test #14:

score: 0
Accepted
time: 13ms
memory: 3384kb

input:

1000 1000
36 A
12 A
72 A
68 A
25 A
18 A
27 A
52 A
20 A
66 A
15 A
14 A
13 A
29 B
38 A
30 B
24 A
17 A
...

output:

516
515
514
474
474
474
475
438
411
412
424
404
368
362
377
400
365
352
354
354
354
345
345
344
311
...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 17ms
memory: 3384kb

input:

1000 1000
10 A
50 A
14 A
72 A
6 A
26 A
24 A
29 A
65 A
65 A
67 A
17 B
0 A
16 A
60 A
64 A
66 A
29 A
27...

output:

499
422
446
430
350
408
314
287
278
267
268
283
276
276
275
251
251
257
198
192
196
220
176
200
200
...

result:

ok 1000 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #16:

score: 35
Accepted
time: 261ms
memory: 22772kb

input:

10000 10000
38 A
49 A
67 A
60 A
62 A
74 A
31 A
6 A
18 A
23 A
45 A
25 A
37 A
62 A
59 A
70 A
71 A
4 A
...

output:

8481
6987
5555
4171
3408
2277
3351
3046
2441
1321
1328
2040
1303
932
1371
1087
1094
1548
1548
925
15...

result:

ok 10000 numbers

Test #17:

score: 0
Accepted
time: 992ms
memory: 65856kb

input:

30000 30000
38 A
49 A
67 A
60 A
62 A
74 A
31 A
6 A
18 A
23 A
45 A
25 A
37 A
62 A
59 A
70 A
71 A
4 A
...

output:

26871
24611
15656
11163
15669
13968
12964
11293
11339
10586
10586
9096
10933
9996
8370
6666
4011
399...

result:

ok 30000 numbers

Test #18:

score: 0
Accepted
time: 3627ms
memory: 216640kb

input:

100000 100000
38 A
49 A
67 A
60 A
62 A
74 A
31 A
6 A
18 A
23 A
45 A
25 A
37 A
62 A
59 A
70 A
71 A
4 ...

output:

95217
86813
82800
79403
85571
80346
77269
78115
72592
77667
74516
73511
70808
72044
72684
72684
7271...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 3496ms
memory: 216640kb

input:

100000 100000
69 A
24 A
24 A
31 A
25 A
57 A
28 A
43 A
15 A
65 A
45 A
9 A
58 A
20 A
61 A
38 A
68 A
39...

output:

85409
91145
91145
87566
77777
78281
78281
75231
76104
75973
73410
73519
73457
70945
70780
68025
6795...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 3548ms
memory: 216640kb

input:

100000 100000
6 A
32 A
30 A
46 A
36 A
41 A
61 A
61 A
32 A
72 A
74 A
60 A
39 A
3 A
4 A
15 A
12 A
41 A...

output:

80582
84214
78557
76782
76653
69364
71611
70822
67509
67753
62043
68747
67218
60747
60747
61124
6112...

result:

ok 100000 numbers

Test #21:

score: -35
Time Limit Exceeded

input:

100000 100000
13 B
15 B
17 B
11 B
56 B
5 B
2 B
3 B
17 B
19 B
46 B
9 B
17 B
19 B
12 B
2 B
18 A
5 B
54...

output:

19329
19232
19032
18844
18846
18862
18815
18763
18716
18617
18489
18371
18474
18357
18345
18120
1809...

result:

Subtask #3:

score: 35
Accepted

Test #26:

score: 35
Accepted
time: 441ms
memory: 65848kb

input:

30000 30000
38 A
49 A
67 A
60 A
62 A
74 A
31 A
6 A
18 A
23 A
45 A
25 A
37 A
62 A
59 A
70 A
71 A
4 A
...

output:

23611
23608
23608
23608
23343
23343
23343
23343
23343
23343
23608
23608
23608
23608
23608
23608
2172...

result:

ok 30000 numbers

Test #27:

score: 0
Accepted
time: 2266ms
memory: 216632kb

input:

100000 100000
3 B
15 B
39 B
8 B
5 B
13 B
2 B
4 B
20 B
5 B
21 B
21 B
10 B
22 B
18 B
2 B
29 B
11 B
14 ...

output:

19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
19551
1955...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 2213ms
memory: 216628kb

input:

100000 100000
11 B
58 A
39 B
14 B
67 A
28 A
28 A
47 A
8 B
48 A
10 B
21 B
5 B
27 A
27 A
8 B
53 A
18 A...

output:

48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
48587
4858...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 2137ms
memory: 216628kb

input:

100000 100000
2 A
68 A
58 A
25 B
10 A
10 B
67 A
46 A
16 B
70 A
59 A
21 A
69 A
38 A
54 A
6 A
13 A
11 ...

output:

78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
78093
7809...

result:

ok 100000 numbers

Test #30:

score: 0
Accepted
time: 2151ms
memory: 216628kb

input:

100000 100000
28 A
11 A
38 A
53 A
9 A
29 B
74 A
32 A
18 A
16 A
8 A
15 A
39 B
58 A
30 A
67 A
42 A
44 ...

output:

87028
87028
87028
87028
87028
87028
87027
87027
87027
87027
87027
87027
87027
87027
87027
87027
8702...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 2257ms
memory: 216632kb

input:

100000 100000
19 A
66 A
67 A
65 A
0 A
61 A
61 A
71 A
58 A
58 A
65 A
29 A
9 B
49 A
2 A
53 A
51 A
53 A...

output:

88564
88564
88564
88564
88564
88564
88564
88564
88563
88563
88562
88563
88564
88564
88564
88564
8856...

result:

ok 100000 numbers

Subtask #4:

score: 0
Skipped

中文 English

Server time: 2025-04-05 05:58:14 | 开源项目