20pts线段树求调
查看原帖
20pts线段树求调
1011471
_droplet_楼主2024/10/9 20:05

来了,看了,给了她(评测姬)一份代码,挂了

#include<bits/stdc++.h>
#define sz r-l+1
#define lsz mid-l+1
#define rsz r-mid
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
const int N=400010;
int n,m,tc,rt,a[N],ch[N][2],sum[N],l1[N],r1[N],l0[N],r0[N],mx1[N],mx0[N],chn[N],rev[N];

void pushup(int x,int l,int r){
	int mid=(l+r)>>1;
	l0[x]=(mx0[ls]==lsz)?lsz+l0[rs]:l0[ls];
	l1[x]=(mx1[ls]==lsz)?lsz+l1[rs]:l1[ls];
	r0[x]=(mx0[rs]==rsz)?rsz+r0[ls]:r0[rs];
	r1[x]=(mx1[rs]==rsz)?rsz+r1[ls]:r1[rs];
	mx0[x]=max({mx0[ls],mx0[rs],r0[ls]+l0[rs]});
	mx1[x]=max({mx1[ls],mx1[rs],r1[ls]+l1[rs]});
	sum[x]=sum[ls]+sum[rs];
}

void pushdown(int x,int l,int r){
	int mid=(l+r)>>1;
	if(chn[x]==1){
		mx0[ls]=l0[ls]=r0[ls]=lsz;
		mx0[rs]=l0[rs]=r0[rs]=rsz;
		mx1[ls]=l1[ls]=r1[ls]=sum[ls]=0;
		mx1[rs]=l1[rs]=r1[rs]=sum[rs]=0;
		chn[ls]=chn[rs]=1;
		rev[ls]=rev[rs]=0;
		chn[x]=rev[x]=0;
	}else if(chn[x]==2){
		mx1[ls]=l1[ls]=r1[ls]=sum[ls]=lsz;
		mx1[rs]=l1[rs]=r1[rs]=sum[rs]=rsz;
		mx0[ls]=l0[ls]=r0[ls]=0;
		mx0[rs]=l0[rs]=r0[rs]=0;
		chn[ls]=chn[rs]=2;
		rev[ls]=rev[rs]=0;
		chn[x]=rev[x]=0;
	}else if(rev[x]){
		sum[ls]=lsz-sum[ls];
		sum[rs]=rsz-sum[rs];
		swap(mx1[ls],mx0[ls]);
		swap(mx1[rs],mx0[rs]);
		swap(l1[ls],l0[ls]);
		swap(l1[rs],l0[rs]);
		swap(r1[ls],r0[ls]);
		swap(r1[rs],r0[rs]);
		if(chn[ls]==0) rev[ls]^=1;
		else if(chn[ls]==1) chn[ls]=2;
		else chn[ls]=1;
		if(chn[rs]==0) rev[rs]^=1;
		else if(chn[rs]==1) chn[rs]=2;
		else chn[rs]=1;
		rev[x]=0;
	}
}

void build(int &x,int l,int r){
	x=++tc;
	if(l==r){
		mx1[x]=l1[x]=r1[x]=sum[x]=a[l];
		mx0[x]=l0[x]=r0[x]=(a[l]==0)?1:0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(x,l,r);
}

void update1(int x,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr){
		if(v){
			mx1[x]=l1[x]=r1[x]=sum[x]=sz;
			mx0[x]=l0[x]=r0[x]=0;
			chn[x]=2;
			rev[x]=0;
		}else{
			mx0[x]=l0[x]=r0[x]=sz;
			mx1[x]=l1[x]=r1[x]=sum[x]=0;
			chn[x]=1;
			rev[x]=0;
		}
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) update1(ls,l,mid,ql,qr,v);
	if(mid<qr) update1(rs,mid+1,r,ql,qr,v);
	pushup(x,l,r);
}

void update2(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		sum[x]=sz-sum[x];
		swap(mx1[x],mx0[x]);
		swap(l1[x],l0[x]);
		swap(r1[x],r0[x]);
		rev[x]^=1;
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) update2(ls,l,mid,ql,qr);
	if(mid<qr) update2(rs,mid+1,r,ql,qr);
	pushup(x,l,r);
}

int query1(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return sum[x];
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	int ans=0;
	if(ql<=mid) ans+=query1(ls,l,mid,ql,qr);
	if(mid<qr) ans+=query1(rs,mid+1,r,ql,qr);
	return ans;
}

int query2(int x,int l,int r,int ql,int qr){
	if(ql==l&&r==qr) return mx1[x];
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(qr<=mid) return query2(ls,l,mid,ql,qr);
    if(mid<ql) return query2(rs,mid+1,r,ql,qr);
	return max({min(l1[rs],qr-mid)+min(r1[ls],mid-ql+1),query2(ls,l,mid,ql,mid),query2(rs,mid+1,r,mid+1,qr)});
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(rt,1,n);
	while(m--){
		int op,l,r;
		cin>>op>>l>>r;
		l++; r++;
		if(op==0) update1(1,1,n,l,r,0);
		if(op==1) update1(1,1,n,l,r,1);
		if(op==2) update2(1,1,n,l,r);
		if(op==3) cout<<query1(1,1,n,l,r)<<"\n";
		if(op==4) cout<<query2(1,1,n,l,r)<<"\n";
//		cout<<"\t";
//		for(int i=1;i<=4*n;i++) cout<<i<<"\t";
//		cout<<"\nls:\t"; for(int x=1;x<=19;x++) cout<<ls<<"\t";
//		cout<<"\nrs:\t"; for(int x=1;x<=19;x++) cout<<rs<<"\t";
//		cout<<"\nl0:\t"; for(int x=1;x<=19;x++) cout<<l0[x]<<"\t";
//		cout<<"\nl1:\t"; for(int x=1;x<=19;x++) cout<<l1[x]<<"\t";
//		cout<<"\nr0:\t"; for(int x=1;x<=19;x++) cout<<r0[x]<<"\t";
//		cout<<"\nr1:\t"; for(int x=1;x<=19;x++) cout<<r1[x]<<"\t";
//		cout<<"\nmx0:\t"; for(int x=1;x<=19;x++) cout<<mx0[x]<<"\t";
//		cout<<"\nmx1:\t"; for(int x=1;x<=19;x++) cout<<mx1[x]<<"\t";
//		cout<<"\nsum:\t"; for(int x=1;x<=19;x++) cout<<sum[x]<<"\t";
//		cout<<"\n\n";
	}
	return 0;
}
2024/10/9 20:05
加载中...