50分求调

#include<bits/stdc++.h>
#define int long long  
using namespace std;
int pos[1000001],st[1000001],ed[1000001],a[1000001],b[1000001],add[100010],n,m,t;
void change(int l,int r,int d){
	if(pos[l]==pos[r]){
		for(int i=st[pos[l]];i<=ed[pos[l]];i++)b[i]=a[i];
		for(int i=l;i<=r;i++){a[i]+=d;b[i]+=d;}
		sort(b+st[pos[l]],b+ed[pos[r]]+1);
		return ;
	}
	else {
		for(int i=pos[l]+1;i<pos[r];i++)add[i]+=d;
		for(int i=st[pos[l]];i<=ed[pos[l]];i++)b[i]=a[i];
		for(int i=l;i<=ed[pos[l]];i++){a[i]+=d;b[i]+=d;}
		for(int i=st[pos[r]];i<=ed[pos[r]];i++)b[i]=a[i];
		for(int i=st[pos[r]];i<=r;i++){a[i]+=d;b[i]+=d;}
		sort(b+st[pos[l]],b+ed[pos[l]]+1);
		sort(b+st[pos[r]],b+ed[pos[r]]+1);
	}
	return ;
}
int ef(int l,int r,int sum,int c){
	int ans1=r+1,k=r;
	while(l<=r){
		int mid=(l+r)/2;
		if(b[mid]+sum<c)l=mid+1;
		else ans1=min(ans1,mid),r=mid-1; 
	}
	return k-ans1+1;
	}
int query(int l,int r,int c){
	int num1=pos[l],num2=pos[r],ans=0;
	if(num1==num2){
		for(int i=l;i<=r;i++)if(a[i]+add[num1]>=c)ans++;
		return ans;
}
	else {
		for(int i=l;i<=ed[num1];i++)if(a[i]+add[num1]>=c)ans++;
		for(int i=st[num2];i<=r;i++)if(a[i]+add[num2]>=c)ans++;
		for(int i=num1+1;i<num2;i++)ans+=ef(st[i],ed[i],add[i],c);
	}
	return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int len=sqrt(n);
for(int i=1;i<=n;i++){
	cin>>a[i];
	b[i]=a[i];
	pos[i]=(i-1)/len+1;
}
t=len;
for(int i=1;i<=len;i++){
	st[i]=(i-1)*len+1;
	ed[i]=i*len;
	}
if(n%len){
	t++;
	st[t]=len*len+1;
	ed[t]=n;
}
for(int i=1;i<=t;i++)sort(b+st[i],b+ed[i]+1);
while(m--){
	char op;
	cin>>op;
	if(op=='M'){
		int l,r,w;
		cin>>l>>r>>w;
		change(l,r,w);
	}
	else {
		int l,r,c;
		cin>>l>>r>>c;
		cout<<query(l,r,c)<<'\n';
	}
}

return 0;
}