「BZOJ3343」教主的魔法

Description

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是NN个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1122\cdotsNN
每个人的身高一开始都是不超过10001000的正整数。教主的魔法每次可以把闭区间[L,R][L,R] (1LRN)(1\leq L\leq R \leq N)内的英雄的身高全部加上一个整数WW。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)L(R)个英雄的身高)
CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L,R][L,R] 内有多少英雄身高大于等于CC,以验证教主的魔法是否真的有效。
WD巨懒,于是他把这个回答的任务交给了你。

Input

11行为两个整数NNQQQQ为问题数与教主的施法数总和。
22行有NN个正整数,第ii个数代表第ii个英雄的身高。
33到第Q+2Q+2行每行有一个操作:
(1) 若第一个字母为M,则紧接着有三个数字L、R、W。表示对闭区间 [L,R][L, R] 内所有英雄的身高加上W。
(2) 若第一个字母为A,则紧接着有三个数字LLRRCC。询问闭区间 [L,R][L, R] 内有多少英雄的身高大于等于CC

Output

对每个A询问输出一行,仅含一个整数,表示闭区间 [L,R][L, R] 内身高大于等于CC的英雄数。

Sample Input

1
2
3
4
5
5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

Sample Output

1
2
2
3

HINT

30%30\%的数据,N1000,Q1000N\leq 1000,Q\leq 1000
100%100\%的数据,N1000000,Q3000N\leq 1000000,Q\leq 3000,1W10001\leq W\leq 1000,1C1,000,000,0001\leq C\leq 1,000,000,000

Solution

块内排序,分块随便搞一搞。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 1200000, B = 1200;
int n, Q;
int a[N];
int L[N], R[N], tot, b[N];
int c[B][B], w[N];
char op[6];

void update(int l, int r, int v) {
int cnt = 0;
if(b[l] == b[r]) {
for(int i = l; i <= r; ++i)
a[i] += v;
for(int i = L[b[l]]; i <= R[b[l]]; ++i)
c[b[l]][++cnt] = a[i] + w[b[l]];
w[b[l]] = 0;
sort(c[b[l]] + 1, c[b[l]] + 1 + cnt);
return;
}
for(int i = b[l] + 1; i < b[r]; ++i) w[i] += v;
for(int i = l; i <= R[b[l]]; ++i) a[i] += v;
for(int i = L[b[l]]; i <= R[b[l]]; ++i)
c[b[l]][++cnt] = a[i] + w[b[l]];
w[b[l]] = 0;
sort(c[b[l]] + 1, c[b[l]] + 1 + cnt);
for(int i = r; i >= L[b[r]]; --i) a[i] += v;
cnt = 0;
for(int i = L[b[r]]; i <= R[b[r]]; ++i)
c[b[r]][++cnt] = a[i] + w[b[r]];
w[b[r]] = 0;
sort(c[b[r]] + 1, c[b[r]] + 1 + cnt);
}
int ask(int x, int v) {
int l = 0, r = R[x] - L[x] + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(v <= c[x][mid]) r = mid;
else l = mid;
}
if(c[x][r] < v) return 0;
return R[x] - L[x] + 1 - r + 1;
}
int query(int l, int r, int c) {
int res = 0;
if(b[l] == b[r]) {
for(int i = l; i <= r; ++i)
res += (a[i] + w[b[l]] >= c);
return res;
}
for(int i = b[l] + 1; i < b[r]; ++i) res += ask(i, c - w[i]);
for(int i = l; i <= R[b[l]]; ++i) res += (a[i] + w[b[l]] >= c);
for(int i = r; i >= L[b[r]]; --i) res += (a[i] + w[b[r]] >= c);
return res;
}
int main() {
n = read(), Q = read();
for(int i = 1; i <= n; ++i) a[i] = read();
tot = sqrt(n);
int cnt = 0;
for(int i = 1; i <= tot; ++i) {
L[i] = cnt + 1;
for(int j = 1; j <= tot; ++j)
b[++cnt] = i;
R[i] = cnt;
}
if(R[tot] < n) {++tot; L[tot] = R[tot - 1] + 1, R[tot] = n;
for(int i = L[tot]; i <= R[tot]; ++i) b[i] = tot;}
for(int i = 1; i <= tot; ++i) {
cnt = 0;
for(int j = L[i]; j <= R[i]; ++j)
c[i][++cnt] = a[j];
sort(c[i]+1,c[i]+1+cnt);
}
while(Q--) {
scanf("%s", op);
int x = read(), y = read(), v = read();
if(op[0] == 'M') {
update(x, y, v);
} else {
writeln(query(x, y, v));
}
}
return 0;
}