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。
分析：对于修改，我们可以对两头进行直接加，然后排序，中间的打一个标记（不会影响序列的有序）。对于每个块二分出第一比c大的即可。
代码：
/************************************************************** Problem: 3343 User: beginend Language: C++ Result: Accepted Time:4780 ms Memory:20848 kb ****************************************************************/ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> const int N=1e6+7; const int maxn=1e3+7; using namespace std; int block,sum,belong[N],l[maxn],r[maxn],x,y,n,m; long long add[maxn],a[N],b[N],c; int i; char op; void kp(int l,int r) { if (l>r) return; int i=l; int j=r; int temp; int key=b[(l+r)/2]; while (i<=j) { while (b[i]<key) i++; while (b[j]>key) j--; if (i<=j) { temp=b[i]; b[i]=b[j]; b[j]=temp; i++; j--; } } kp(l,j); kp(i,r); } void build_block() { block=trunc(sqrt(n))+1; sum=n/block; if (n%block) sum++; for (i=1;i<=sum;i++) { l[i]=(i-1)*block+1; r[i]=i*block; } r[sum]=n; for (i=1;i<=n;i++) { belong[i]=(i-1)/block+1; b[i]=a[i]; } for (i=1;i<=sum;i++) { kp(l[i],r[i]); } } void updata(int x,int y,long long c) { int j; int s=belong[x]; if (belong[x]==belong[y]) { for (j=l[s];j<=r[s];j++) { a[j]+=add[s]; if ((x<=j) && (j<=y)) { a[j]+=c; } b[j]=a[j]; } kp(l[s],r[s]); add[s]=0; return; } for (j=l[s];j<=r[s];j++) { a[j]+=add[s]; if (x<=j) { a[j]+=c; } b[j]=a[j]; } kp(l[s],r[s]); int t=belong[y]; for (j=l[t];j<=r[t];j++) { a[j]+=add[t]; if (j<=y) { a[j]+=c; } b[j]=a[j]; } kp(l[t],r[t]); add[s]=add[t]=0; for (j=s+1;j<t;j++) add[j]+=c; } int ask(int x,int y,long long c) { int j,ans=0; int s=belong[x]; int t=belong[y]; if (belong[x]==belong[y]) { for (j=x;j<=y;j++) { if (a[j]+add[s]>=c) ans++; } return ans; } for (j=x;j<=r[s];j++) { if (a[j]+add[s]>=c) ans++; } for (j=l[t];j<=y;j++) { if (a[j]+add[t]>=c) ans++; } int k,ll,rr; for (j=s+1;j<t;j++) { ll=l[j]; rr=r[j]; k=r[j]+1; while (ll<=rr) { int mid=(ll+rr)/2; if (b[mid]>=c-add[j]) { rr=mid-1; k=mid; } else ll=mid+1; } ans+=r[j]-k+1; } return ans; } int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&a[i]); build_block(); for (i=1;i<=m;i++) { scanf("%s",&op); if (op=='M') { scanf("%d%d%lld",&x,&y,&c); updata(x,y,c); } else { scanf("%d%d%lld",&x,&y,&c); printf("%d\n",ask(x,y,c)); } } } 