洛谷P2801 教主的魔法 题解

发表于 | 分类于

题意：
给定一个长度为 $n$ 序列和 $m$ 次操作，每次操作可以把一段区间内的每一个数都加上一个指定的数，或查询一段区间内的数有多少个大于某个指定的数。

分块板子题。

首先在每个块内把块内元素排序。

对于修改操作，可以把整块打上标记，零散块暴力修改排序。

对于查询操作，可以在整块内二分，零散块暴力查询。

细节较多，稍不留神就写错了……

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

using namespace std;

int tag[1010], n, q, block_size, a[1000010], blcnt, l[1010], r[1010], b[1000010];

inline bool is_digit(char c) {
	return c <= '9' && c >= '0';
}

inline int read() {
	int tmp = 0;
	char c = getchar();
	while(!is_digit(c)) c = getchar();
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp;
}

inline void write(int x) {
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48); 
}

inline void subtask1() {
	while(q--) {
		char opt = getchar();
		while(!isalpha(opt)) opt = getchar();
		int l = read(), r = read(), c = read();
		if(opt == 'M') {
			for(register int i = l; i <= r; i++) a[i] += c;
		} else {
			int ans = 0;
			for(register int i = l; i <= r; i++) 
				if(a[i] >= c) ans++;
			write(ans), putchar(10);
		}
	}
	exit(0);
}

int main() {
	n = read(), q = read();
	for(register int i = 1; i <= n; i++) b[i] = a[i] = read();
	block_size = sqrt(n);
	blcnt = n / block_size;
	for(register int i = 1; i <= blcnt; i++) l[i] = (i - 1) * block_size + 1, r[i] = i * block_size;
	if(n % block_size) {
		blcnt++;
		l[blcnt] = r[blcnt - 1] + 1;
		r[blcnt] = n;
	}
	for(register int i = 1; i <= blcnt; i++) sort(b + l[i], b + r[i] + 1);
	while(q--) {
		char opt = getchar();
		while(!isalpha(opt)) opt = getchar();
		int ql = read(), qr = read(), c = read();
		int lbl = (ql + block_size - 2) / block_size + 1;
		int rbl = (qr - 1) / block_size;
		// cout << lbl << " " << rbl << endl;
		if(opt == 'A') {
			int ans = 0;
			for(register int i = lbl; i <= rbl; i++) {
				int lb = l[i], rb = r[i], res = -1;
				while(lb <= rb) {
					int mid = (lb + rb) >> 1;
					if(b[mid] + tag[i] >= c) {
						rb = mid - 1;
						res = mid;
					} else {
						lb = mid + 1;
					}
				}
				if(res != -1) ans += r[i] - res + 1;
			}
			int ll = l[lbl], rr = r[rbl];
			if(lbl <= rbl) {
				if(ql < ll) {
					for(register int i = ql; i < ll; i++) {
						if(a[i] + tag[lbl - 1] >= c) ans++;
					}
				}
				if(qr > rr) {
					for(register int i = rr + 1; i <= qr; i++) {
						if(a[i] + tag[rbl + 1] >= c) ans++;
					}
				}
				write(ans), putchar(10);
			} else {
				for(register int i = ql; i <= qr; i++) {
					if(a[i] + tag[lbl - 1] >= c) ans++;
				}
				write(ans), putchar(10);
			}
		} else {
			for(register int i = lbl; i <= rbl; i++) tag[i] += c;
			int ll = l[lbl], rr = r[rbl];
			if(lbl <= rbl) {
				if(ql < ll) {
					for(register int i = ql; i <= r[lbl - 1]; i++) a[i] += c;
					for(register int i = l[lbl - 1]; i <= r[lbl - 1]; i++) b[i] = a[i];
						sort(b + l[lbl - 1], b + r[lbl - 1] + 1); 
				}
				if(qr > rr) {
					for(register int i = l[rbl + 1]; i <= qr; i++) a[i] += c;
					for(register int i = l[rbl + 1]; i <= r[rbl + 1]; i++) b[i] = a[i];
					sort(b + l[rbl + 1], b + r[rbl + 1] + 1);
				}
			} else {
				for(register int i = ql; i <= qr; i++) a[i] += c;
				for(register int i = l[lbl - 1]; i <= r[lbl - 1]; i++) b[i] = a[i];
				sort(b + l[lbl - 1], b + r[lbl - 1] + 1); 
			}
		}
	}
	return 0;
}