关于数据

RT。刚刚写了一个非常错误的做法，然后直接过了......

关于这个做法：像题解里面那样块内二分，但是我并没有存下来原来的数组是什么样的，也就是直接对块内进行排序了。

显然，在排序后会打乱块内原有元素的位置，然后暴力分块查询的时候应该出错。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<string>
#include<cstring>
#include<set>
#include<stack>
#include<queue>
#include<bitset>
using namespace std;
namespace IO{
    template<typename T>inline void read(T &x){
        x=0;
        char ch=getchar();
        bool flag=0;
        while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
        while(ch>='0'&&ch<='9') x=x*10+(ch^'0'),ch=getchar();
        if(ch!='.'){
            x=flag?-x:x;
            return;
        }
        double Base=0.1;
        while(ch<'0'||ch>'9') ch=getchar();
        while(ch>='0'&&ch<='9') x=x+Base*(ch^'0'),Base/=10.0,ch=getchar();
        x=flag?-x:x;
    }
    template<typename T>void prt(T x){
        if(x>9) prt(x/10);
        putchar(x%10+'0');
    }
    template<typename T>inline void put(char ch,T x){
        if(x<0) putchar('-'),x=-x;
        prt(x);
        putchar(ch);
    }
    const int DM[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
    inline void putd(char ch,double x,int w){
        if(x<0) putchar('-'),x=-x;
        if(!w){
            put(ch,(int)(x+0.5));
            return;
        }
        int prex=(int)x;
        x-=(int)x;
        x*=DM[w];
        x+=0.5;
        int nowx=(int)x,now=0;
        if(nowx>=DM[w]) nowx=0,prex++;
        put('.',prex);
        int xx=nowx;
        if(!xx) now=1;
        else while(xx) xx/=10,now++;
        now=w-now;
        while(now--) putchar('0');
        put(ch,nowx);
    }
    inline void putstr(string s){
        for(int i=0;i<s.length();i++) putchar(s[i]);
    }
    inline bool getch(){
        char ch=getchar();
        while(ch!='M'&&ch!='A') ch=getchar();
        return ch=='M';
    }
}
using namespace IO;
#define N 2000005
int n,q,bel[N],L[N],R[N],len,w[N],lg;
int now[N],tag[N];
inline void rebuild(int l,int r,int k){//l~r这个段，断点为k 
    if(k>r) return;
    for(int i=l;i<=r;i++) now[i]=w[i];
    int i=l,j=k,t=l;
    while(i<k&&j<=r)
        if(now[i]>now[j]) w[t++]=now[j++];
        else w[t++]=now[i++];
    while(i<k) w[t++]=now[i++];
    while(j<=r) w[t++]=now[j++];
    for(int i=l;i<=r;i++) now[i]=0;
}
inline void update(int l,int r,int num){
    int bl=bel[l],br=bel[r];
    if(bl==br){
        for(int i=l;i<=r;i++) w[i]+=num;
        rebuild(L[l],r,l);
        rebuild(L[l],R[l],r+1);
        return;
    }
    for(int i=l;i<=R[l];i++) w[i]+=num;
    rebuild(L[l],R[l],l);
    for(int i=L[r];i<=r;i++) w[i]+=num;
    rebuild(L[r],R[r],r+1);
    for(int i=bl+1;i<br;i++) tag[i]+=num;
}
inline int query(int l,int r,int k){
    int bl=bel[l],br=bel[r],res=0;
    if(bl==br){
        for(int i=l;i<=r;i++)
            res+=(w[i]+tag[bl]>=k);
        return res;
    }
    for(int i=l;i<=R[l];i++) res+=(w[i]+tag[bl]>=k);
    for(int i=L[r];i<=r;i++) res+=(w[i]+tag[br]>=k);
    for(int i=bl+1;i<br;i++){
        int ll=(i-1)*len+1,rr=i*len,lst=i*len+1;
        while(ll<=rr){
            int mid=ll+rr>>1;
            if(tag[i]+w[mid]>=k) rr=mid-1,lst=mid;
            else ll=mid+1;
        }
        res+=i*len-lst+1;
    }
    return res;
}
int main(){
    memset(w,0x3f,sizeof(w));
    read(n),read(q);
    lg=log(n);
    len=sqrt(n*lg)+1;
    for(int i=1,beg=1,num=1,id=1;i<=n;i++,num++){
        bel[i]=id,L[i]=beg,R[i]=beg+len-1;
        if(num==len) num=0,id++,beg=i+1;
    }
    for(int i=1;i<=n;i++) read(w[i]);
    for(int i=1;i<=n;i=R[i]+1) sort(w+L[i],w+R[i]+1);
    for(int i=1,op,x,y,c;i<=q;i++){
        op=getch(),read(x),read(y),read(c);
        if(op) update(x,y,c);
        else put('\n',query(x,y,c));
    }
    return 0;
}