bzoj2453

传送门：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));

     }

 }