传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2453
题目大意：
（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。
题解：分块+二分咯
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 1000001
using namespace std;
int add[maxn],a[maxn],b[maxn],pos[maxn];
char ch[];
int n,m,blo,num;
int read()
{
int x=; char ch; bool bo=;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') bo=;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
if (bo) return -x; return x;
}
void resort(int x)
{
int l=(x-)*blo+,r=min(x*blo,n);
for (int i=l; i<=r; i++)
b[i]=a[i];
sort(b+l,b+r+);
}
int find(int x,int v)
{
int l=(x-)*blo+,r=min(x*blo,n);
int last=r;
while (l<=r)
{
int mid=(l+r)>>;
if (b[mid]<v) l=mid+;
else r=mid-;
}
return last-l+;
}
int query(int x,int y,int v)
{
int sum=;
if (pos[x]==pos[y])
{
for (int i=x; i<=y; i++)
if (a[i]+add[pos[i]]>=v) sum++;
}
else
{
for(int i=x;i<=pos[x]*blo;i++)
if(a[i]+add[pos[i]]>=v)sum++;
for(int i=(pos[y]-)*blo+;i<=y;i++)
if(a[i]+add[pos[i]]>=v)sum++;
}
for (int i=pos[x]+; i<pos[y]; i++)
sum+=find(i,v-add[i]);
return sum;
}
void ins(int x,int y,int v)
{
if (pos[x]==pos[y])
{
for (int i=x; i<=y; i++) a[i]+=v;
}
else
{
for (int i=x; i<=blo*pos[x]; i++) a[i]+=v;
for (int i=(pos[y]-)*blo+; i<=y; i++) a[i]+=v;
}
resort(pos[x]); resort(pos[y]);
for (int i=pos[x]+; i<pos[y]; i++)
add[i]+=v;
}
int main()
{
n=read(); m=read();
blo=int(sqrt(n));
for (int i=; i<=n; i++) a[i]=b[i]=read(),pos[i]=(i-)/blo+;
num=(n-)/blo+;
for (int i=; i<=num; i++) resort(i);
for (int i=; i<=m; i++)
{
scanf("%s",ch+); int x=read(),y=read(),z=read();
if (ch[]=='M') ins(x,y,z);
else printf("%d\n",query(x,y,z));
}
}