题目链接：https://loj.ac/problem/6278
题目描述
给出一个长为 (n) 的数列，以及 (n) 个操作，操作涉及区间加法，询问区间内小于某个值 (x) 的元素个数。
输入格式
第一行输入一个数字 (n)。
第二行输入 (n) 个数字，第 (i) 个数字为 (a_i)，以空格隔开。
接下来输入 (n) 行询问，每行输入四个数字 (opt)、(l)、(r)、(c)，以空格隔开。
若 (opt=0)，表示将位于 ([l,r]) 的之间的数字都加 (c)。
若 (opt=1)，表示询问 ([l,r]) 中，小于 (c^2) 的数字的个数。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例输入
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
样例输出
3
0
2
解题思路
同样还是按照每个块的大小为 (lfloor sqrt{n}
floor) 来进行分块。
这里我们同样用 (p[i]) 来表示 (a[i]) 所属的分块编号，用 (v[k]) 来表示第 (k) 个分块的累计更新值。
于此同时，我们再开一个数组 (b[i]) ，(b) 数组其实就是 (a) 数组的一个映射。那么它是怎么映射的呢？
我们假设 (a[l..r]) 属于同一个分块，且 (a[l] 是这个分块的第一个元素，)a[r$ 是这个分块的最后一个元素，那么 (b[l..r]) 就是 (a[l..r]) 排好序的结果，即：
- (b[l]) 对应 (a[l..r]) 中最小的元素；
- (b[l+1]) 对应 (a[l..r]) 中次小的元素；
- ……
- (b[r]) 对应 (a[l..r]) 中最大的元素。
一旦我们修改了某一个分块 (k) 中的部分元素，就需要将分块 (k) 对应的 (b) 数组的这段区间排序（对于分块 (k)，它对应的坐标范围应该是 ([(k-1) imes m + 1, min(k imes m, n)])）。
修改操作：
- 如果区间没有完整覆盖分块 (k)，则遍历次分块中的每一个元素，令 (a[i]+=c)；
- 否则（完整覆盖分块 (k)），则令 (v[k] += c)。
查询操作：
- 如果区间没有完整覆盖分块 (k)，则遍历次分块中的每一个元素，判断 (a[i] lt c^2-v[p[i]]) 是否成立；
- 否则（完整覆盖分块 (k)），因为 (b) 数组具有单调性，对分块 (k) 包含的区间范围内的 (b[l..r]) 进行二分获取有多少元素 (b[i] lt c^2-v[k])。
最后将答案汇总。
每次修改的时间复杂度为 (O( sqrt{n} ))；
每次查询的时间复杂度为 (O( sqrt{n} imes sqrt{ sqrt{n} } ) = O(n^{ frac 34 })) ，
因为总共有有 (n) 次操作，所以整的时间复杂度为 (O(n imes n^{ frac 34 })) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50050;
int n, m, a[maxn], b[maxn], p[maxn], v[300], op, l, r, c;
void update_part(int pid) {
int i1 = (pid-1)*m+1, i2 = min(pid*m+1, n+1); // 一定要注意边界条件，我在这里RE了好久，因为最后一个分块长度不一定是m
for (int i = i1; i < i2; i ++)
b[i] = a[i];
sort(b+i1, b+i2);
}
void add(int l, int r, int c) {
if (p[l] == p[r]) { // 说明在同一个分块，直接更新
for (int i = l; i <= r; i ++) a[i] += c;
update_part(p[l]);
return;
}
if (l % m != 1) { // 说明l不是分块p[l]的第一个元素
for (int i = l; p[i]==p[l]; i ++) {
a[i] += c;
}
update_part(p[l]);
}
else v[p[l]] += c;
if (r % m != 0) { // 说明r不是分块p[r]的最后一个元素
for (int i = r; p[i]==p[r]; i --)
a[i] += c;
update_part(p[r]);
}
else v[p[r]] += c;
for (int i = p[l]+1; i < p[r]; i ++)
v[i] += c;
}
int count_part(int pid, int c) {
int i1 = (pid-1)*m+1, i2 = min(pid*m+1, n+1);
int cnt = lower_bound(b+i1, b+i2, c*c-v[pid]) - (b+i1);
return cnt;
}
int get_count(int l, int r, int c) {
int cnt = 0;
if (p[l] == p[r]) { // 说明在同一个分块，直接更新
for (int i = l; i <= r; i ++)
if (a[i]+v[p[i]] < c*c)
cnt ++;
return cnt;
}
if (l % m != 1) { // 说明l不是分块p[l]的第一个元素
for (int i = l; p[i]==p[l]; i ++)
if (a[i]+v[p[i]] < c*c)
cnt ++;
}
else cnt += count_part(p[l], c);
if (r % m != 0) { // 说明r不是分块p[r]的最后一个元素
for (int i = r; p[i]==p[r]; i --)
if (a[i]+v[p[i]] < c*c)
cnt ++;
}
else cnt += count_part(p[r], c);
for (int i = p[l]+1; i < p[r]; i ++)
cnt += count_part(i, c);
return cnt;
}
int main() {
scanf("%d", &n);
m = sqrt(n);
for (int i = 1; i <= n; i ++) p[i] = (i-1)/m + 1;
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = m; i <= n; i += m) update_part(p[i]); // 初始化所有完整的块
for (int i = 0; i < n; i ++) {
scanf("%d%d%d%d", &op, &l, &r, &c);
if (op == 0) add(l, r, c);
else printf("%d
", get_count(l, r, c));
}
return 0;
}