有n个数，两种操作M和A：
M：将l到r中所有的数增加w
A：询问l到r中有多少大于等于c的数
考虑分块
可以将询问大于等于c的数的个数转化为,在有序数列中二分查找c的位置
设置b数组初始值等于对应的a，块内排序
M操作等同于普通分块
A操作：
1、对于整块，查找大于等于c-add的数的个数
2、对于边角，将add下放到a数组，用a数组更新b数组，然后暴力询问
（发现将无序转有序可以解决很多问题）
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <queue> #include <vector> #include <map> #include <cstdlib> #include <ctime> using namespace std; #define ll long long #define ull unsigned long long #define Rll register ll #define ld long double #define lowbit(x) ((x) & (-x)) #define For(x, i, j) for (register int x = (i); x <= (j); x++) #define FOR(x, i, j) for (register int x = (i); x >= (j); x--) #define ls(o) (o << 1) #define rs(o) (o << 1 | 1) #define debug(x) cout << "debug : " << x << endl; inline int read() { int x = 0, w = 1; char ch = getchar(); 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; } #define N 1000005 int n, m, a[N], b[N], add[N], pos[N], blo, tot, L[N], R[N]; void change(int l, int r, int w) { int p = pos[l], q = pos[r]; if (q - p <= 1) { For(i, l, R[p]) a[i] += add[p]; For(i, L[q], r) a[i] += add[q]; For(i, l, r) a[i] += w; For(i, L[p], l - 1) a[i] += add[p]; For(i, r + 1, R[q]) a[i] += add[q]; add[p] = add[q] = 0; For(i, L[p], R[q]) b[i] = a[i]; sort(b + L[p], b + R[p] + 1); sort(b + L[q], b + R[q] + 1); } else { For(i, l, R[p]) a[i] += add[p]; For(i, L[q], r) a[i] += add[q]; For(i, l, r) a[i] += w; For(i, L[p], l - 1) a[i] += add[p]; For(i, r + 1, R[q]) a[i] += add[q]; add[p] = add[q] = 0; For(i, L[p], R[p]) b[i] = a[i]; For(i, L[q], R[q]) b[i] = a[i]; sort(b + L[p], b + R[p] + 1); sort(b + L[q], b + R[q] + 1); For(i, p + 1, q - 1) add[i] += w; } } int check(int x, int y, int c) { int l = x, r = y, mid; while (l <= r) { mid = (l + r) >> 1; if (b[mid] + add[pos[mid]] >= c) r = mid - 1; else l = mid + 1; } return y - l + 1; } int query(int l, int r, int c) { int p = pos[l], q = pos[r], ret = 0; if (q - p <= 1) { For(i, l, r) if (a[i] + add[pos[i]] >= c) ret++; } else { For(i, l, R[p]) if (a[i] + add[p] >= c) ret++; For(i, L[q], r) if (a[i] + add[q] >= c) ret++; For(i, p + 1, q - 1) { ret += check(L[i], R[i], c); } } return ret; } int main() { n = read(); m = read(); getchar(); For(i, 1, n) a[i] = read(), b[i] = a[i]; getchar(); blo = sqrt(n); tot = n / blo; For(i, 1, n) pos[i] = (i - 1) / blo + 1; For(i, 1, tot) L[i] = (i - 1) * blo + 1, R[i] = i * blo; if (R[tot] < n) tot++, L[tot] = R[tot - 1] + 1, R[tot] = n; For(i, 1, tot) { sort(b + L[i], b + R[i] + 1); } while (m--) { char op[3]; scanf("%s", op); if (op[0] == ‘M‘) { int l = read(), r = read(), w = read(); change(l, r, w); } else { int l = read(), r = read(), c = read(); printf("%d\n", query(l, r, c)); } getchar(); } return 0; }
原文：https://www.cnblogs.com/FL4K/p/14343028.html