题目大意:有$n$个数,$q$个操作。两种操作:
- $M\;l\;r\;w:$把$[l,r]$所有数加上$w$
- $A\;l\;r\;c:$查询$[l,r]$内大于等于$c$的元素的个数。
题解:分块,对于在整块修改改$tag$,非整块暴力修改,查询整块用$lower\_bound$,非整块暴力
卡点:无
C++ Code:
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 1000010
int n, Q, bsz, num;
int l[1010], r[1010], tg[1010];
struct node {
int w, id;
inline bool operator < (const node &rhs) const {return w < rhs.w;}
} s[maxn];
int main() {
scanf("%d%d", &n, &Q); bsz = sqrt(n);
for (int i = 1; i <= n; i++) scanf("%d", &s[i].w), s[i].id = i;
num = n / bsz + 1;
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * bsz;
if (i == 1) l[i] = 1;
r[i] = i * bsz - 1;
if (i == num) r[i] = n;
std::sort(s + l[i], s + r[i] + 1);
}
while (Q --> 0) {
char op[10];
int x, y, z;
scanf("%s%d%d%d", op, &x, &y, &z);
int lb = x / bsz + 1, rb = y / bsz + 1;
if (op[0] == 'M') {
if (lb == rb) {
for (int i = l[lb]; i <= r[lb]; i++) {
s[i].w = tg[lb];
if (s[i].id >= x && s[i].id <= y) s[i].w += z;
}
tg[lb] = 0;
std::sort(s + l[lb], s + r[lb]);
} else {
for (int i = l[lb]; i <= r[lb]; i++) {
s[i].w += tg[lb];
if (s[i].id >= x) s[i].w += z;
}
std::sort(s + l[lb], s + r[lb] + 1);
for (int i = lb + 1; i < rb; i++) tg[i] += z;
for (int i = l[rb]; i <= r[rb]; i++) {
s[i].w += tg[lb];
if (s[i].id <= y) s[i].w += z;
}
std::sort(s + l[rb], s + r[rb] + 1);
tg[lb] = tg[rb] = 0;
}
} else {
int ans = 0;
if (lb == rb) {
for (int i = l[lb]; i <= r[lb]; i++) {
s[i].w += tg[lb];
if (s[i].id >= x && s[i].id <= y && s[i].w >= z) ans++;
}
tg[lb] = 0;
} else {
for (int i = l[lb]; i <= r[lb]; i++) {
s[i].w += tg[lb];
if (s[i].id >= x && s[i].w >= z) ans++;
}
for (int i = lb + 1; i < rb; i++) {
ans += s + r[i] - std::lower_bound(s + l[i], s + r[i] + 1, (node) {z - tg[i], 0}) + 1;
}
for (int i = l[rb]; i <= r[rb]; i++) {
s[i].w += tg[rb];
if (s[i].id <= y && s[i].w >= z) ans++;
}
tg[lb] = tg[rb] = 0;
}
printf("%d\n", ans);
}
}
return 0;
}