分塊二分——BZO3343 教主的魔法

題面：BZOJ3343

分塊二分大暴力！

以前初三剛學分塊的時候以為這題很難QAQ，現在認為……

這題實在是water到不知道哪裡去了666

我們對于資料分塊，然後對塊内的數進行排序

修改的時候發現如果整個塊都被覆寫在區間裡面的話，那麼就對整個塊進行标記（因為整個塊内的數都被加上了）

兩邊多出來的暴力修改，然後再次對塊内進行排序

排序的原因是詢問時要對塊進行二分

詢問還是老辦法，對于一整個塊的資料我們二分找比要求的數大的個數（這就是排序的原因），對于多出來的暴力統計

時間複雜度大約是 O(Qn√∗logn)

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
    int k=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*+ch-'0';ch=getchar();}
    return k*f;
}
inline void write(int x){
    if(x<)putchar('-'),x=-x;
    if(x>)write(x/);putchar(x%+'0');
}
inline void writeln(int x){
    write(x);puts("");
}
int n,m,c,p,a[],w[]={},b[]={},sum[]={};
inline void yu(int x){
    int l=(x-)*p+,r=min(n,x*p);
    for(int i=l;i<=r;i++)b[i]=a[i];
    sort(b+l,b+r+);
}
inline void add(int x,int y,int z){
    if(w[x]==w[y])for(int i=x;i<=y;i++)a[i]+=z;
    else{
        for(int i=x;i<=w[x]*p;i++)a[i]+=z;
        for(int i=(w[y]-)*p+;i<=y;i++)a[i]+=z;
    }
    yu(w[x]);yu(w[y]);
    for(int i=w[x]+;i<w[y];i++)sum[i]+=z;
}
inline int erfen(int x,int v){
    int l=(x-)*p+,r=min(n,x*p);int la=r;
    while(l<=r){
        int mm=(l+r)/;
        if(b[mm]<v)l=mm+;
        else r=mm-;
    }
    return la-l+;
}
inline int ssum(int x,int y,int z){
    int ans=;
    if(w[x]==w[y]){for(int i=x;i<=y;i++)if(a[i]+sum[w[i]]>=z)ans++;}
    else{
        for(int i=x;i<=w[x]*p;i++)if(a[i]+sum[w[i]]>=z)ans++;
        for(int i=(w[y]-)*p+;i<=y;i++)if(a[i]+sum[w[i]]>=z)ans++;
    }
    for(int i=w[x]+;i<w[y];i++)ans+=erfen(i,z-sum[i]);
    return ans;
}
int main()
{
    n=read();c=read();
    p=(int)(sqrt(n));
    for(int i=;i<=n;i++){
        a[i]=read();
        w[i]=(i-)/p+;
        b[i]=a[i];
    }
    if(n%p==)m=n/p;
    else m=n/p+;
    for(int i=;i<=m;i++)yu(i);
    for(int i=;i<=c;i++){
        char ss[];scanf("%s",ss);int x=read(),y=read(),z=read();
        if(ss[]=='M')add(x,y,z);
        else writeln(ssum(x,y,z));
    }
    return ;
}