# 解题思路
修改，就是一个区间修改的常规操作，但是为了迎合查询的需要，对两端的不完整的块需要暴力重构，重新进行排序操作，保证每一块都是单调上升的顺序。
然后再说进行查询的操作，起初，我们需要在每一个块内进行排序。保证顺序时单调上升的（在每一个块内，是独立的），然后查询的时候对每一块（$k$）都二分查找到大于 $num + tag[k]$ 的第一个数的位置，然后就可以得到一共有多少大于 $num$ 的数了。
值得注意的是，有些题解写的是对原序列直接进行排序，这就有一个错误，那就是在排序之后序列的顺序改变，改变了之后在进行区间修改的时候就不能保证正确性了。
所以我们开一个 vector 将每个块内的数都存下来。我的代码 T 了一个点，但是了 O2 过了，懒得再去卡常了
# 附上代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1e6+
3;
int N, Q, arr[maxn],
in[maxn], cnt, tag[maxn];
vector<
int> b[
1003];
struct BLOCK {
template <typename T> inline
void read(T &
x) {
x =
0; T f =
1;
char c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1; c =
getchar();}
while (c <=
'9' && c >=
'0') {x = x*
10 + c-
'0'; c =
getchar();}
x *=
f;
}
void reset(
int k) {
b[k].clear();
for(
int i=(k-
1)*cnt+
1; i<=min(k*cnt, N); i++
)
arr[i] +=
tag[k], b[k].push_back(arr[i]);
sort(b[k].begin(), b[k].end());
tag[k] =
0;
}
void build() {
cnt =
sqrt(N);
for(
int i=
1; i<=N; i++
) {
read(arr[i]);
in[i] = (i-
1)/cnt+
1;
b[in[i]].push_back(arr[i]);
}
for(
int i=
in[
1]; i<=
in[N]; i++
)
sort(b[i].begin(), b[i].end());
}
void update(
int l,
int r,
int num) {
for(
int i=l; i<=min(
in[l]*cnt, r); i++
)
arr[i] +=
num;
reset(in[l]);
if(
in[l] !=
in[r]) {
for(
int i=(
in[r]-
1)*cnt+
1; i<=r; i++
)
arr[i] +=
num;
reset(in[r]);
}
for(
int i=
in[l]+
1; i<
in[r]; i++
)
tag[i] +=
num;
}
int check(
int k,
int num) {
int ans = (b[k].end()-lower_bound(b[k].begin(), b[k].end(), num-
tag[k]));
return ans;
}
int query(
int l,
int r,
int num) {
int ans =
0;
for(
int i=l; i<=min(
in[l]*cnt, r); i++
)
if(arr[i] + tag[
in[i]] >= num) ans ++
;
if(
in[l] !=
in[r]) {
for(
int i=(
in[r]-
1)*cnt+
1; i<=r; i++
)
if(arr[i] + tag[
in[i]] >= num) ans ++
;
}
for(
int i=
in[l]+
1; i<
in[r]; i++
)
ans +=
check(i, num);
return ans;
}
BLOCK () {
read(N), read(Q);
build();
char opt;
int l, r, num;
for(
int i=
1; i<=Q; i++
) {
cin>>
opt;
read(l), read(r), read(num);
if(opt ==
'M') update(l, r, num);
else printf(
"%d\n", query(l, r, num));
}
}
}BLO;
int main() {}
转载于:https://www.cnblogs.com/bljfy/p/9789981.html
相关资源：数据结构—成绩单生成器
