题解：P13977 数列分块入门 2
Lonelyhacker
·
·
题解
题意
给出一个长为 n 的数列，以及 n 个操作，操作有两种（\mathrm{opt}\in\{0,1\}），涉及：
- 区间加（\mathrm{opt}=0），令 \forall i \in [l,r],a_i \leftarrow a_i+c。
- 区间查询（\mathrm{opt}=1），询问 \forall i \in [l,r],a_i < c^2 的 a_i 的个数。
## 题解
区间加还是很好写的，如果还不会写建议先回去写 [P13976 数列分块入门 1](https://www.luogu.com.cn/problem/P13976) 熟悉分块。
至于区间查询，我们也可以用分块的思想 —— 将操作分成整块和散块（散点）进行操作。
对于整块，我们可以直接用 `lower_bound` 找到第一个 $\ge c^2$ 的位置，假设为 $pos$，则显然这个整块中有 $\forall i \in [1,pos],a_i < c^2$，即有 $pos$ 个 $< c^2$ 的 $a_i$，累加到计数器即可。当然我们肯定要维护所有整块的单调性，我此处用了 `vector` 维护，详见代码。
对于散块（散点），直接暴力查询，将其值与其所在块的懒标记相加，若 $< c^2$ 则计数器累加 $1$。
然后记得修改操作时，要对修改后的散块（散点）所在的块重新排序，因为这些点修改后可能打破其所在整块的单调性。
## 代码
我保留了之前写的注释，可能？会有所帮助罢。
还有提醒一下：十年 OI。
```cpp
// 核心思路：散块暴力找单点，整块（有序）二分查找
// 对一个块进行修改后，让整个块有序
// 整块轻松，散块就先按下标排回来，然后暴力单点修改，然后再按权值重新排序
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n, blo, bl[N];
ll v[N], atag[N];
vector <ll> vec[N]; // 用来存排序后的块们
void resort(int x){ // 散块改变后，其所在的整块全部重新排序
vec[x].clear(); // 清空后遍历从块头到块尾
for (int i = (x-1)*blo+1; i <= min(x*blo, n); i++) // min防越界
vec[x].push_back(v[i]);
sort(vec[x].begin(), vec[x].end()); // 记得排序
}
void add(int a, int b, int c){ // 与第一个相同
// 对散块进行修改后要记得对散块所在的整块进行重新排序
for (int i = a; i <= min(bl[a]*blo, b); i++)
v[i] += c;
resort(bl[a]); // 记住传的是bl[其所在的块]
if (bl[a] != bl[b]){
for (int i = (bl[b]-1)*blo+1; i <= b; i++)
v[i] += c;
resort(bl[b]);
}
for (int i = bl[a]+1; i <= bl[b]-1; i++)
atag[i] += c;
}
int query(int a, int b, ll c){
int res = 0; // 记录数据
// 以下同add差不多，就是记得给散块的点加上其所在的！修改量atag
for (int i = a; i <= min(bl[a]*blo, b); i++)
if (v[i]+atag[bl[a]] < c) res++;
if (bl[a] != bl[b])
for (int i = (bl[b]-1)*blo+1; i <= b; i++)
if (v[i]+atag[bl[b]] < c) res++; // 别脑抽把atag[bl[b]]写成bl[a]了
for (int i = bl[a]+1; i <= bl[b]-1; i++){
ll x = c-atag[i]; // 记得要先减去atag[i] 因为在vector里面仅仅是v[i]，他们的atag尚未下传 还有这里要开Longlong
res += lower_bound(vec[i].begin(), vec[i].end(), x)-vec[i].begin();
}
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
blo = sqrt(n);
for (int i = 1; i <= n; i++){
cin >> v[i];
bl[i] = (i-1)/blo+1;
vec[bl[i]].push_back(v[i]); // 全部进vector
}
for (int i = 1; i <= bl[n]; i++) // 给所有块排序
sort(vec[i].begin(), vec[i].end());
for (int i = 1, f, a, b, c; i <= n; i++){
cin >> f >> a >> b >> c;
if (f == 0) add(a, b, c);
else cout << query(a, b, 1ll*c*c) << '\n'; // 别忘了是求c*c
}
return 0;
}
```