[文章目录]
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巨懒，于是他把这个回答的任务交给了你。
分块。
将序列分为根号n块，每个块有根号n个元素。对块内元素排序，然后每个块维护一个加数的标记。对每个块查询的复杂度为√n*log√n。修改的复杂度为√n+log√n。
自带大常数。。。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rint register int
using namespace std;
inline int read(int &x)
{
x=0; char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
int n,m,blo,lz[1100],w[1001000],bl[1001000];
int a[1001000];
bool cmp(int x,int y) {return w[x]<w[y];}
int query(int x,int y)
{
y-=lz[bl[x]];
rint l=x*blo,r=x*blo+blo,mid;
while(l<r)
{
mid=l+r>>1;
if(w[a[mid]]>=y) r=mid;
else l=mid+1;
}
return x*blo+blo-r;
}
int main()
{
read(n); read(m);
rint i; blo=sqrt(n*1.0)+1;
for(i=0;i!=n;++i)
read(w[i]),a[i]=i,bl[i]=i/blo;
for(i=0;i<n;i+=blo) sort(a+i,a+i+blo,cmp);
char sw[10]; rint ans,x,y,val,tmp;
while(m--)
{
scanf("%s",sw);read(x); read(y); read(val); x--; y--;
if(sw[0]=='M')
{
tmp=bl[x]; while(x<=y&&x%blo!=0) w[x]+=val,x++;
if(bl[x]!=tmp) sort(a+tmp*blo,a+min(n,tmp*blo+blo),cmp);
tmp=bl[y]; while(x<=y&&y%blo!=blo-1) w[y]+=val,y--;
if(bl[y]!=tmp) sort(a+tmp*blo,a+min(n,tmp*blo+blo),cmp);
if(x<=y)
{
x=bl[x]; y=bl[y];
while(x<=y) lz[x++]+=val;
}
}
else
{
ans=0;
while(x<=y&&x%blo!=0) {if(w[x]+lz[bl[x]]>=val) ans++; x++;}
while(x<=y&&y%blo!=blo-1) {if(w[y]+lz[bl[y]]>=val) ans++; y--;}
if(x<=y)
{
x=bl[x]; y=bl[y];
while(x<=y) ans+=query(x,val),x++;
}
printf("%d\n",ans);
}
}
return 0;
}