3343: 教主的魔法
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1312 Solved: 585[][][]Description
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是 N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、 N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[ L, R]（1≤ L≤ R≤ N）内的英雄的身高全部加上一个整数 W。（虽然 L= R时并不符合区间的书写规范，但我们可以认为是单独增加第 L（ R）个英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [ L, R] 内有多少英雄身高大于等于 C，以验证教主的魔法是否真的有效。
WD巨懒，于是他把这个回答的任务交给了你。
Input
第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。
Output
对每个“A”询问输出一行，仅含一个整数，表示闭区间 [ L, R] 内身高大于等于 C的英雄数。
Sample Input
5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4
Sample Output
2 3
HINT
【输入输出样例说明】
原先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。
Source
思路:
分块以后，对于每个询问区间[L,R]，对于收尾两个区间进行暴力寻找即可。对于中间的块，我们提前进行排序然后进行二分寻找大于c-add[now_block_id]即可（因为每个块是sqrt(n)个元素，所以总的复杂度应该是n*sqrt(n)*log(n)）
//看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#includeusing namespace std;#pragma comment(linker,"/STACK:102400000,102400000")#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const int maxn = 1000000 + 5;int n, q;int block, num, belong[maxn], L[maxn], R[maxn];int add[maxn], a[maxn], d[maxn];void build_block(){ block = sqrt(n * 1.0); num = n / block; if (n % block) num++; for (int i = 1; i <= num; i++){ L[i] = (i - 1) * block + 1, R[i] = i * block; } R[num] = n; for (int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1; for (int i = 1; i <= num; i++){ sort(d + L[i], d + R[i] + 1); }}void modify(int l, int r){ for (int i = l; i <= r; i++) d[i] = a[i]; sort(d + l, d + r + 1);}void update(int ql, int qr, int w){ if (belong[ql] == belong[qr]){ for (int i = ql; i <= qr; i++) a[i] += w; modify(L[belong[ql]], R[belong[ql]]); return ; } for (int i = ql; i <= R[belong[ql]]; i++) a[i] += w; modify(L[belong[ql]], R[belong[ql]]); for (int i = L[belong[qr]]; i <= qr; i++) a[i] += w; modify(L[belong[qr]], R[belong[qr]]); for (int i = belong[ql] + 1; i < belong[qr]; i++) add[i] += w;}int query(int ql, int qr, int c){ int ans = 0; if (belong[ql] == belong[qr]){ for (int i = ql; i <= qr; i++) if (c - add[belong[ql]] <= a[i]) ans++; return ans; } for (int i = ql; i <= R[belong[ql]]; i++) if (c - add[belong[ql]] <= a[i]) ans++; for (int i = L[belong[qr]]; i <= qr; i++) if (c - add[belong[qr]] <= a[i]) ans++; for (int i = belong[ql] + 1; i < belong[qr]; i++){ int l = L[i], r = R[i]; int p = lower_bound(d + l, d + r + 1, c - add[i]) - d; ans += r + 1 - p; } return ans;}int main(){ cin >> n >> q; for (int i = 1; i <= n; i++){ scanf("%d", a + i); d[i] = a[i]; } build_block(); while (q--){ char ch[2]; int a, b, c; scanf("%s%d%d%d", ch, &a, &b, &c); if (ch[0] == 'A'){ printf("%d\n", query(a, b, c)); } else update(a, b, c); } return 0;}