萌新刚学分块请求帮助!
查看原帖
萌新刚学分块请求帮助!
590571
_weishiqi66_楼主2024/3/8 17:35

RT 犯了很多错误,改了很多,但是还是有问题。请求打了帮助

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7;

int t, n, a[N];
int ll[N],rr[N],pos[N];
int add[N],v[N];

inline int read() {
	int x=0,f=1;
	char ch; ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') f*-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x= x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

inline bool cmp(int x,int y) { return x<y; }

inline void reset(int x) {
	for(int i=ll[x];i<=rr[x];i++) v[i]=a[i];
	sort(v+ll[x],v+rr[x]+1,cmp);
} 

inline void change(int l,int r,int c) {
	int p=pos[l],q=pos[r];
	if(p==q) {
		for(int i=l;i<=r;i++) a[i]+=c;
		reset(p);
	} 
	else {
		for(int i=p+1;i<=q-1;i++) add[i]+=c;
		for(int i=l;i<=rr[p];i++) a[i]+=c;
		reset(p);
		for(int i=ll[q];i<=r;i++) a[i]+=c;
		reset(q);
	}
	return ;
}

inline int ef(int l,int r,int x) {
	int ll=l;
	while(l<r) {
		int mid=(l+r)/2;
		if(v[mid]>=x) r=mid;
		else l=mid+1;
	}
	
	if(v[l]>=x) return 0;
	return ll-l+1;
}

inline int ask(int l,int r,int c) {
	int p=pos[l],q=pos[r];
	int ans=0;
	if(p==q) {
		for(int i=l;i<=r;i++) {
			if(a[i]+add[p] >= c) 	ans++;
		}
		return ans;
	}
	else {
		for(int i=p+1;i<=q-1;i++) ans+=ef(ll[i],rr[i],c);
		for(int i=l;i<=rr[p];i++) if(a[i]+add[p] >= c) ans++;
		for(int i=ll[q];i<=r;i++) if(a[i]+add[q] >= c) ans++;
		return ans;
	}
}

int main() {
	n=read(); int T=read();
	for(int i=1;i<=n;i++) {
		a[i]=read();
		v[i]=a[i];
	}
	
	t=sqrt(n);
	for(int i=1;i<=t;i++) {
		ll[i]=(i-1)*t+1;
		rr[i]=i*t;
		for(int j=ll[i];j<=rr[i];j++) pos[j]=i;
		sort(v+ll[i],v+rr[i]+1,cmp);
	}
	if(rr[t]<n){
		t++; ll[t]=rr[t-1]+1; rr[t]=n;
	}
	
	while(T--){
		char Q; cin>>Q;
		int l, r, c; l=read();r=read();c=read();
		if(Q=='M') change(l, r, c);
		else cout<<ask(l,r,c)<<endl; 
	}
	return 0;
}
2024/3/8 17:35
加载中...