教主的魔法

问题：

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。

每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）

CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。

WD巨懒，于是他把这个回答的任务交给了你。

 

解：

分块板题

动态区间第k小数

复习一下分块

code:

//  
#include<stdio.h>
#include<bits/stdc++.h>  
using namespace std;  
#define maxnn 2000000  
int n,Q;  
int laz[maxnn];  
int a[maxnn];  
int s;  
int k1,k2;  
int B[6000][6000];  
int cnt[6000];  

  inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
void modify(int x,int y,int z)  
{  
     k1=(x-1)/s+1;  
     k2=(y-1)/s+1;  
    if(k1==k2)  
    {  
        for(int i=x;i<=y;i++)  
        {
            a[i]=a[i]+z;
        }
        cnt[k1]=0;
        for(int i=(k1-1)*s+1;i<=k1*s;i++)
        {
            B[k1][cnt[k1]]=a[i];
            cnt[k1]++;
        }
    }  
    else  
    {  
        for(int i=x;i<=k1*s;i++)  
        {
            a[i]=a[i]+z;
        }
        cnt[k1]=0;
        for(int i=(k1-1)*s+1;i<=k1*s;i++)
        {
            B[k1][cnt[k1]]=a[i];
            cnt[k1]++;
        }
        
         for(int i=(k2-1)*s+1;i<=y;i++)  
        {
            a[i]=a[i]+z;
        }
         cnt[k2]=0;
        for(int i=(k2-1)*s+1;i<=k2*s;i++)
        {
            B[k2][cnt[k2]]=a[i];
            cnt[k2]++;
        }
        for(int i=k1+1;i<k2;i++)  
        {  
            laz[i]+=z;   
        }  
    }  
    
        sort(B[k1],B[k1]+cnt[k1]);    
           sort(B[k2],B[k2]+cnt[k2]);  
}  
int query(int x,int y,int z)  
{  
    int k1=(x-1)/s+1;  
    int k2=(y-1)/s+1;  
    int ans=0;  
    if(k1==k2)  
    {  
        for(int i=x;i<=y;i++)  
        {  
            if(a[i]+laz[k1]>=z) ans++;  
        }  
    }  
    else  
    {  
        for(int i=x;i<=k1*s;i++)  
        if(a[i]+laz[k1]>=z) ans++;  
        for(int i=(k2-1)*s+1;i<=y;i++)  
        {  
            if(a[i]+laz[k2]>=z) ans++;  
        }  
            for(int i=k1+1;i<k2;i++)  
        {  
            ans+=(cnt[i]-(lower_bound(B[i],B[i]+cnt[i],z-laz[i])-B[i]));  
        }  
    }  
    return ans;  
}  
int main()  
{  
    char ch;  
    
    n=read();
    Q=read();
    
    int x,y,z;  
    for(int i=1;i<=n;i++)  
    {  
       a[i]=read(); 
    }  
     s=int(sqrt(n));  
    for(int i=1;i<=n;i++)  
    {  
        int k=(i-1)/s+1;  
        B[k][cnt[k]]=a[i]; 
        cnt[k]++;  
    }  
    for(int i=1;i<=s+1;i++)  
    {  
        sort(B[i],B[i]+cnt[i]);  
    }  
    while(Q--)  
    {  
        cin>>ch;  
          
        if(ch=='A')  
        {  
            x=read();y=read();
            z=read();  
            cout<<query(x,y,z)<<endl;  
        }  
        else  
        {  
            
            x=read();y=read();
            z=read();   
            modify(x,y,z);  
        }  
    }  
}