RE求助!
查看原帖
RE求助!
209808
银河AI楼主2021/2/25 21:53

分块RE求助,不知道错哪里了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,q,x,y,block,len,k;
int a[N],bel[N],b[N],st[N],ed[N];
char opt;
inline void init(){
	block=sqrt(n);len=ceil((double)n/block);
	for(int i=1;i<=len;i++){
		for(int j=(i-1)*block+1;j<=i*block;j++) bel[j]=i,b[j]=a[j];
		st[i]=(i-1)*block+1,ed[i]=i*block;
		if(i==len) ed[i]=n;
		sort(b+st[i],b+ed[i]+1);
	}
}
inline void add(int x,int k){
	a[x]=k;
	for(int i=st[bel[x]];i<=ed[bel[x]];i++) b[i]=a[i];
	sort(b+st[bel[x]],b+ed[bel[x]]+1);
}
inline int ask(int l,int r,int k){
	int ans=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++) if(a[i]<=k) ans++;
		return ans;
	}
	for(int i=l;i<=ed[bel[l]];i++) if(a[i]<=k) ans++;
	for(int i=st[bel[r]];i<=r;i++) if(a[i]<=k) ans++;
	for(int i=bel[l]+1;i<bel[r];i++){
		int anss=st[i]-1,tmp=st[i],ll=st[i],rr=ed[i];
		while(ll<=rr){
			int mid=(ll+rr)>>1;
			if(b[mid]<=k) anss=mid,ll=mid+1;
			else rr=mid-1;
		}
		ans+=anss-tmp+1;
	}
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	init();
	while(q--){
		cin>>opt;//scanf("%s",opt);
		if(opt=='M') scanf("%lld%lld",&x,&y),add(x,y);
		else scanf("%lld%lld%lld",&x,&y,&k),printf("%lld\n",ask(x,y,k));
	}
}
2021/2/25 21:53
加载中...