题目地址：洛谷：【P2801】教主的魔法 – 洛谷、BZOJ：Problem 3343. — 教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。
WD巨懒，于是他把这个回答的任务交给了你。

题意简述

给一个序列，两种操作

1. 区间加一个数
2. 区间询问不小于k的数的个数

输入输出格式

输入格式：
第1行为两个整数N、Q。Q为问题数与教主的施法数总和。
第2行有N个正整数，第i个数代表第i个英雄的身高。
第3到第Q+2行每行有一个操作：
（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

输出格式：
对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。

输入输出样例

输入样例#1：

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

输出样例#1：

2
3

说明

【输入输出样例说明】
原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。
【数据范围】
对30%的数据，N≤1000，Q≤1000。
对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。

题解

考虑分块解决这个问题。我们对每个块内部排序，查询的时候整块就二分查找，边角暴力。修改的时候整块打标记，边角暴力。注意重构块的时候要重新从原数组中复制过来，因为原数组和排序后的块的下标并不一一对应。
总复杂度O(q \sqrt{n} \log n)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'M' || c == 'A';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

const int MAXN = 1000005;

int n, q, block, bn, a[MAXN], b[MAXN], bid[MAXN], l[MAXN], r[MAXN], tag[MAXN];

inline void rebuild(int bno) {
    for(int i = l[bno]; i <= r[bno]; i++) {
        b[i] = a[i];
    }
    std::sort(b + l[bno], b + r[bno] + 1);
}

inline void modify(int ll, int rr, int v) {
    if(bid[ll] == bid[rr]) {
        for(int i = ll; i <= rr; i++) {
            a[i] += v;
        }
        rebuild(bid[ll]); return;
    }
    for(int i = ll; i <= r[bid[ll]]; i++) {
        a[i] += v;
    }
    rebuild(bid[ll]);
    for(int i = l[bid[rr]]; i <= rr; i++) {
        a[i] += v;
    }
    rebuild(bid[rr]);
    for(int i = bid[ll] + 1; i < bid[rr]; i++) {
        tag[i] += v;
    }
}

inline int query(int ll, int rr, int v) {
    int res = 0;
    if(bid[ll] == bid[rr]) {
        for(int i = ll; i <= rr; i++) {
            if(a[i] + tag[bid[ll]] >= v) res++;
        }
        return res;
    }
    for(int i = ll; i <= r[bid[ll]]; i++) {
        if(a[i] + tag[bid[ll]] >= v) res++;
    }
    for(int i = l[bid[rr]]; i <= rr; i++) {
        if(a[i] + tag[bid[ll]] >= v) res++;
    }
    for(int i = bid[ll] + 1; i < bid[rr]; i++) {
        res += (b + r[i]) - std::lower_bound(b + l[i], b + r[i] + 1, v - tag[i]) + 1;
    }
    return res;
}

char op; int ll, rr, v;

int main() {
    n = readint(); q = readint(); block = sqrt(n); bn = (n + block - 1) / block;
    for(int i = 1; i <= n; i++) {
        a[i] = readint(); bid[i] = (i - 1) / block + 1;
    }
    for(int i = 1; i <= bn; i++) {
        l[i] = (i - 1) * block + 1; r[i] = std::min(i * block, n); rebuild(i);
    }
    while(q--) {
        op = readop(); ll = readint(); rr = readint(); v = readint();
        if(op == 'M') {
            modify(ll, rr, v);
        } else {
            printf("%d\n", query(ll, rr, v));
        }
    }
    return 0;
}