题目描述
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给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行为两个整数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的英雄数。
样例输入
5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4
样例输出
2 3
题解
分块+二分
分成√n 个块，对于每个块另开一个数组将h[i]排序。
修改时，整块直接打add标记，多余部分暴力改，然后重排序。
查询时，整块使用排序后的数组二分查找大于等于c-add的个数，多余部分暴力查询。
注意l和r同块时的特判。
#include#include #include using namespace std;int n , si , h[1000010] , v[1000010] , add[1010];char str[5];void reset(int b){ int i , l = b * si , r = min((b + 1) * si - 1 , n - 1); for(i = l ; i <= r ; i ++ ) v[i] = h[i]; sort(v + l , v + r + 1);}int search(int b , int lim){ int l = b * si , r = min((b + 1) * si - 1 , n - 1) , mid , ans = r + 1 , tr = r; while(l <= r) { mid = (l + r) >> 1; if(v[mid] + add[b] >= lim) ans = mid , r = mid - 1; else l = mid + 1; } return tr - ans + 1;}int main(){ int m , i , l , r , x , ans; scanf("%d%d" , &n , &m); si = (int)sqrt(n); for(i = 0 ; i < n ; i ++ ) scanf("%d" , &h[i]); for(i = 0 ; i * si < n ; i ++ ) reset(i); while(m -- ) { scanf("%s%d%d%d" , str , &l , &r , &x); l -- , r -- ; if(str[0] == 'M') { if(l / si == r / si) { for(i = l ; i <= r ; i ++ ) h[i] += x; reset(l / si); } else { for(i = l / si + 1 ; i < r / si ; i ++ ) add[i] += x; for(i = l ; i < (l / si + 1) * si ; i ++ ) h[i] += x; for(i = r / si * si ; i <= r ; i ++ ) h[i] += x; reset(l / si) , reset(r / si); } } else { ans = 0; if(l / si == r / si) for(i = l ; i <= r ; i ++ ) ans += (h[i] + add[l / si] >= x); else { for(i = l / si + 1 ; i < r / si ; i ++ ) ans += search(i , x); for(i = l ; i < (l / si + 1) * si ; i ++ ) ans += (h[i] + add[l / si] >= x); for(i = r / si * si ; i <= r ; i ++ ) ans += (h[i] + add[r / si] >= x); } printf("%d\n" , ans); } } return 0;}