警示后人:如果你一直20分
查看原帖
警示后人:如果你一直20分
444290
wallace_QwQ楼主2025/1/10 23:40

这是本蒟蒻写代码时的所有bug,调了一个晚上,发出来希望能够帮到大家

问题全在注释里了

int n,q,B;
int a[N],b[N];
int idx[N],pos[N];
int t[N],tot;
int ans;
int bl[M],br[M];
int tag[M];
int to[N];
struct node{
	int id;//原下标
	int s;//s[i]=suma[i]-sumb[i]
	int w;
	int sw;
}p[N];
void build(int i){
	sort(p+bl[i],p+br[i]+1,[](node nd1,node nd2){
		return nd1.s<nd2.s;
	});
	p[bl[i]].sw=p[bl[i]].w;
	for1(j,bl[i],br[i]){
		to[p[j].id]=j;
		if(j!=bl[i])
			p[j].sw=p[j-1].sw+p[j].w;//mistake2:前缀处理不当 
	}
}
void ins(int x){
	int idd=x/B;
	for1(i,x,br[idd]){
		ans+=1ll*p[to[i]].w*(p[to[i]].s+tag[idd]>=0?1:-1);
		p[to[i]].s++;//mistake3:s打成w 
	}
	build(idd);//mistake4:忘记加build 
	for1(i,idd+1,tot/B){//mistake5:tot打成n 
		int l=bl[i],r=br[i],res=-1;
		while(l<=r){
			int mid=l+r>>1;
			if(p[mid].s+tag[i]>=0) res=mid,r=mid-1;
			else l=mid+1;
		}
		if(res==-1) ans-=p[br[i]].sw;
		else if(res==bl[i]) ans+=p[br[i]].sw;//mistake6:bl打成br 
		else {
			ans-=p[res-1].sw;
			ans+=p[br[i]].sw-p[res-1].sw;
		}
		tag[i]++;
	}
}
void del(int x){
	int idd=x/B;
	for1(i,x,br[idd]){
		ans+=1ll*p[to[i]].w*(p[to[i]].s+tag[idd]<=0?1:-1);
		p[to[i]].s--;//mistake3:s打成w 
	}
	build(idd);
	for1(i,idd+1,tot/B){//mistake5:tot打成n 
		int l=bl[i],r=br[i],res=-1;
		while(l<=r){
			int mid=l+r>>1;
			if(p[mid].s+tag[i]<=0) res=mid,l=mid+1;
			else r=mid-1;
		}
		if(res==-1) ans-=p[br[i]].sw;
		else if(res==br[i]) ans+=p[br[i]].sw;
		else {
			ans+=p[res].sw;
			ans-=p[br[i]].sw-p[res].sw;
		}
		tag[i]--;
	}
}
void solve(){
	cin>>n; 
	for1(i,1,n) cin>>a[i],t[++tot]=a[i];
	for1(i,1,n) cin>>b[i],t[++tot]=b[i];
	cin>>q;
	for1(i,1,q) cin>>idx[i]>>pos[i],t[++tot]=pos[i];
	sort(t+1,t+1+tot);
	tot=unique(t+1,t+1+tot)-t-1;
	auto val=[&](int x)->int{return lower_bound(t+1,t+1+tot,x)-t;};
	for1(i,1,n) p[val(a[i])].s++,p[val(b[i])].s--;
	t[tot+1]=t[tot];
	for1(i,1,tot) p[i].w=t[i+1]-t[i],p[i].s+=p[i-1].s,ans+=abs(p[i].s)*p[i].w,p[i].id=i;//mistake2:前缀处理不当 
	cout<<ans<<"\n";
	B=sqrt(tot),bl[0]++;
	for1(i,0,tot/B)
		bl[i]+=i*B,br[i]=min((i+1)*B-1,tot);//mistake1: 没有-1 
	for1(i,0,tot/B)
		build(i);
	for1(ii,1,q){
		int xx=val(a[idx[ii]]),yy=val(pos[ii]);
		del(xx);
		ins(yy);
		a[idx[ii]]=pos[ii];
		cout<<ans<<"\n";
	}
	return ;
}
2025/1/10 23:40
加载中...