rt

提交记录

我用的分块，两个 TLE。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+1;
int n,m,a[N],l[N],r[N],pos[N],add[N],b[1001][1001];
void init(){
	int t=sqrt(n)/2;
	for(int i=1;i<=t;i++){
		l[i]=r[i-1]+1;
		r[i]=i*t*2;
	}
	if(r[t]<n){
		t++;
		l[t]=r[t-1]+1;
		r[t]=n;
	}
	for(int i=1;i<=t;i++){
		for(int j=l[i];j<=r[i];j++){
			 b[i][j-l[i]+1]=a[j];
		}
		sort(b[i]+1,b[i]+1+r[i]-l[i]+1);
	}
	return;
}
void update(int lc,int rc,int c){
	int p=pos[lc],q=pos[rc];
	if(p==q){
		for(int i=lc;i<=rc;i++){
			a[i]+=c;
		}
		for(int i=l[p];i<=r[p];i++){
			b[p][i-l[p]+1]=a[i];
		}
		sort(b[p]+1,b[p]+1+r[p]-l[p]+1);
	}
	else{
		for(int i=lc;i<=r[p];i++){
			a[i]+=c;
		}
		for(int i=l[p];i<=r[p];i++){
			b[p][i-l[p]+1]=a[i];
		}
		sort(b[p]+1,b[p]+1+r[p]-l[p]+1);
		for(int i=p+1;i<q;i++){
			add[i]+=c;
		}
		for(int i=l[q];i<=rc;i++){
			a[i]+=c;
		}
		for(int i=l[q];i<=r[q];i++){
			b[q][i-l[q]+1]=a[i];
		}
		sort(b[q]+1,b[q]+1+r[q]-l[q]+1);
	}
	return;
}
int query(int lc,int rc,int c){
	int p=pos[lc],q=pos[rc],res=0;
	if(p==q){
		for(int i=lc;i<=rc;i++){
			if(a[i]+add[p]>=c){
				res++;
			}
		}
	}
	else{
		for(int i=lc;i<=r[p];i++){
			if(a[i]+add[p]>=c){
				res++;
			}
		}
		for(int i=p+1;i<q;i++){
			res+=lower_bound(b[i]+1,b[i]+1+r[i]-l[i]+1,c-add[i])-b[i]-1;
		}
		for(int i=l[q];i<=rc;i++){
			if(a[i]+add[p]>=c){
				res++;
			}
		}
	}
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	for(int i=1;i<=m;i++){
		int l,r,c;
		char opt;
		cin>>opt>>l>>r>>c;
		if(opt=='M'){
			update(l,r,c);
		}
		else{
			cout<<query(l,r,c)<<endl;
		}
	}
	return 0;
}

如果改成 scanf 和 printf 样例都错了。