记录

开了 O2 会 wa #7 ~ #10 & hack#2

关 O2 会 re #7~#10 & hack#2

非常奇怪，求调

#include<bits/stdc++.h>
using namespace std;
#define il inline
typedef long long LL;
typedef unsigned long long ULL;
#define int LL

namespace FastRead{
	struct InRead{
		template<typename T> T read(){
			T x=0;int f=1,ch=getchar();
			while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
			while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
			return x*f;
		}     
//		template<typename T,typename ...Args> void read(T &x,Args& ...y){x=read<T>();read(y...);}
		template<typename T> InRead& operator>>(T &x){return x=read<T>(),(*this);}
	}in;
	struct OutPut{
		template<typename T> void write(T x){
            int stk[50],cnt=0,f=0;if(x<0)x=-x,f=1;
			do{stk[++cnt]=x%10;x/=10;}while(x);if(f)putchar('-'); 
            while(cnt){putchar(stk[cnt--]|48);}
		}
        OutPut& write(const char&x){return putchar(x),(*this);}
        template<typename T> OutPut& write(T *x){while(*x)putchar(*(x++));return(*this);}
//		template<typename T,typename ...Args> void write(T x,Args ...y){write(x);write(y...);}
		template<typename T> OutPut& operator<<(T x){return write(x),(*this);}
	}out;
}using namespace FastRead;

typedef const int& ci;
#define For(i,t,n) for(int i=t;i<=n;++i)
#define For_(i,t,n) for(int i=t;i>=n;--i)
const int inf=0x3f3f3f3f;
const int MAXN=1e6+5;
const int SQ=1e3+5;
int Len,All;

int n,m;
int a[MAXN],tmp[MAXN];
int tag[SQ],idd[SQ];
int L[SQ],R[SQ];

void storage(ci u){
    For(i,L[u],R[u]) tmp[i]=a[i];
    sort(tmp+L[u],tmp+R[u]+1);
}

void build(ci l,ci r){
    Len=sqrt(n),All=n/Len+(n%Len?1:0);
    For(i,1,All) L[i]=R[i-1]+1,R[i]=L[i]+Len-1;
    R[All]=n;
    For(i,1,All){
        For(j,L[i],R[i]){
            idd[j]=i;
        }
        storage(i);
    }
}

void add(ci l,ci r,ci w){
    int u=idd[l],v=idd[r];
    if(u==v){
        if(l==L[u]&&r==R[u]) tag[u]+=w;
        else{
            For(i,l,r) a[i]+=w;
            storage(u);
        } 
    }else{
        For(i,l,R[u]) a[i]+=w;
        storage(u);
        For(k,u+1,v-1) tag[k]+=w;
        For(i,L[v],r) a[i]+=w;
        storage(v);
    }
}

int bs(ci u,ci w){
    int pos=lower_bound(tmp+L[u],tmp+R[u]+1,w)-(tmp+L[u]);
    return (pos<0?0:Len-pos);
}

int query(ci l,ci r,ci w){
    int u=idd[l],v=idd[r],res=0;
    if(u==v){
        For(i,l,r){
            if(a[i]+tag[u]>=w) ++res;
        }
    }else{
        For(i,l,R[u]){
            if(a[i]+tag[u]>=w) ++res;
        }      
        For(k,u+1,v-1){
            res+=bs(k,w-tag[k]);
        }
        For(i,L[v],r){
            if(a[i]+tag[v]>=w) ++res;
        }              
    }
    return res;
}

void solve(){
    in>>n>>m; 
    For(i,1,n) in>>a[i];
    build(1,n);
    while(m--){
        char op; int l,r,w;
        cin>>op; in>>l>>r>>w;
        if(l>r) swap(l,r);
        if(op=='M'){
            add(l,r,w);
        }else{
            out<<query(l,r,w)<<'\n';
        }
    }
}

signed main(){
	solve();
	return 0;
}