求助,线段树玄学范围出错,70pts,80pts,90pts
查看原帖
求助,线段树玄学范围出错,70pts,80pts,90pts
354308
Bezime楼主2021/8/15 09:45

大佬,我的代码为什么改线段树维护范围会出点问题?

  • 数组范围1~n,线段树范围1~n,70pts,WA2,5,6
#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,pair<ll,ll> > 
#define mp make_pair
#define nd second
#define st first
#define mxn 200002
using namespace std;
struct XD_tree{
	ll l,r,pre0,pre1,ls0,ls1,rs0,rs1,mx0,mx1,lz,rz,len;
}tr[2*mxn];
ll n,m,a[mxn];
ll trt,rrt;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void ppt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) ppt(x/10);putchar(x%10+'0');}
inline void ptup(ll p){
	ll l=tr[p].l,r=tr[p].r,ls0=tr[l].ls0,rs0=tr[r].rs0,ls1=tr[l].ls1,rs1=tr[r].rs1;
	tr[p].pre0=tr[l].pre0+tr[r].pre0;
	tr[p].pre1=tr[l].pre1+tr[r].pre1;
	if(tr[l].ls0==tr[l].len) ls0+=tr[r].ls0;
	if(tr[l].ls1==tr[l].len) ls1+=tr[r].ls1;
	if(tr[r].rs0==tr[r].len) rs0+=tr[l].rs0;
	if(tr[r].rs1==tr[r].len) rs1+=tr[l].rs1;
	tr[p].ls0=ls0;
	tr[p].ls1=ls1;
	tr[p].rs0=rs0;
	tr[p].rs1=rs1;
	tr[p].mx0=max(max(tr[l].rs0+tr[r].ls0,max(tr[l].mx0,tr[r].mx0)),max(tr[p].ls0,tr[p].rs0));
	tr[p].mx1=max(max(tr[l].rs1+tr[r].ls1,max(tr[l].mx1,tr[r].mx1)),max(tr[p].ls1,tr[p].rs1));
	tr[p].lz=-1;
	tr[p].rz=0;
}
inline void doit1(ll p,ll k){
	ll len=tr[p].len;
	if(k){
		tr[p].pre0=0;
		tr[p].pre1=len;
		tr[p].ls0=0;
		tr[p].ls1=len;
		tr[p].rs0=0;
		tr[p].rs1=len;
		tr[p].mx0=0;
		tr[p].mx1=len;
	}else{
		tr[p].pre0=len;
		tr[p].pre1=0;
		tr[p].ls0=len;
		tr[p].ls1=0;
		tr[p].rs0=len;
		tr[p].rs1=0;
		tr[p].mx0=len;
		tr[p].mx1=0;
	}
	tr[p].lz=k;
	tr[p].rz=0;
}
inline void doit2(ll p){
	swap(tr[p].pre0,tr[p].pre1);
	swap(tr[p].ls0,tr[p].ls1);
	swap(tr[p].rs0,tr[p].rs1);
	swap(tr[p].mx0,tr[p].mx1);
	if(tr[p].lz!=-1) tr[p].lz=!tr[p].lz;
	else tr[p].rz=!tr[p].rz;
}
inline void ptdn(ll p){
	ll l=tr[p].l,r=tr[p].r;
	if(tr[p].lz!=-1){
		doit1(l,tr[p].lz);
		doit1(r,tr[p].lz);
	}else if(tr[p].rz){
		doit2(l);
		doit2(r);
	}
	tr[p].lz=-1;
	tr[p].rz=0;
}
inline void bd(ll &p,ll l,ll r){
	if(!p) p=++trt;
	tr[p].len=r-l+1;
	tr[p].lz=-1;
	if(l==r){
		if(a[l]) tr[p].pre1=tr[p].ls1=tr[p].rs1=tr[p].mx1=1;
		else tr[p].pre0=tr[p].ls0=tr[p].rs0=tr[p].mx0=1;
		return;
	}
	ll mid=l+r>>1;
	bd(tr[p].l,l,mid);
	bd(tr[p].r,mid+1,r);
	ptup(p);
}
inline void chg1(ll p,ll l,ll r,ll x,ll y,ll k){
	if(l>y||r<x) return;
	if(l>=x&&r<=y){
		doit1(p,k);
		return;
	}
	ll mid=l+r>>1;
	ptdn(p);
	chg1(tr[p].l,l,mid,x,y,k);
	chg1(tr[p].r,mid+1,r,x,y,k);
	ptup(p);
}
inline void chg2(ll p,ll l,ll r,ll x,ll y){
	if(l>y||r<x) return;
	if(l>=x&&r<=y){
		doit2(p);
		return;
	}
	ll mid=l+r>>1;
	ptdn(p);
	chg2(tr[p].l,l,mid,x,y);
	chg2(tr[p].r,mid+1,r,x,y);
	ptup(p);
}
inline ll ask1(ll p,ll l,ll r,ll x,ll y){
	if(l>y||r<x) return 0;
	if(l>=x&&r<=y) return tr[p].pre1;
	ll mid=l+r>>1,z=0;
	ptdn(p);
	z+=ask1(tr[p].l,l,mid,x,y);
	z+=ask1(tr[p].r,mid+1,r,x,y);
	ptup(p);
	return z;
}
inline pr ask2(ll p,ll l,ll r,ll x,ll y){
	if(l>y||r<x) return mp(0,mp(0,0));
	if(l>=x&&r<=y) return mp(tr[p].mx1,mp(tr[p].ls1,tr[p].rs1));
	ll mid=l+r>>1;
	ptdn(p);
	pr zl=ask2(tr[p].l,l,mid,x,y);
	pr zr=ask2(tr[p].r,mid+1,r,x,y);
	pr z=mp(max(zl.nd.nd+zr.nd.st,max(zl.st,zr.st)),mp(zl.nd.st,zr.nd.nd));
	if(zl.st==mid-x+1) z.nd.st=zl.st+zr.nd.st;
	if(zr.st==y-mid) z.nd.nd=zr.st+zl.nd.nd;
	z.st=max(z.st,max(z.nd.nd,z.nd.st));
	ptup(p);
	return z;
}
int main(){
	rd(n),rd(m);
	for(ll i=1;i<=n;i++)
		rd(a[i]);
	bd(rrt,1,n);
	while(m--){
		ll v,l,r;
		rd(v),rd(l),rd(r);
		l++,r++;
		if(v<2) chg1(rrt,1,n,l,r,v);
		else if(v==2) chg2(rrt,1,n,l,r);
		else if(v==3) ppt(ask1(rrt,1,n,l,r)),puts("");
		else ppt(ask2(rrt,1,n,l,r).st),puts("");
	}
}
  • 数组范围1~n,线段树范围1~200000,80pts,WA1,2
int main(){
	rd(n),rd(m);
	for(ll i=1;i<=n;i++)
		rd(a[i]);
	bd(rrt,1,mxn-2);
	while(m--){
		ll v,l,r;
		rd(v),rd(l),rd(r);
		l++,r++;
		if(v<2) chg1(rrt,1,mxn-2,l,r,v);
		else if(v==2) chg2(rrt,1,mxn-2,l,r);
		else if(v==3) ppt(ask1(rrt,1,mxn-2,l,r)),puts("");
		else ppt(ask2(rrt,1,mxn-2,l,r).st),puts("");
	}
}
  • 数组范围1~n,线段树范围0~200000,90pts,WA5
int main(){
	rd(n),rd(m);
	for(ll i=1;i<=n;i++)
		rd(a[i]);
	bd(rrt,0,mxn-2);
	while(m--){
		ll v,l,r;
		rd(v),rd(l),rd(r);
		l++,r++;
		if(v<2) chg1(rrt,0,mxn-2,l,r,v);
		else if(v==2) chg2(rrt,0,mxn-2,l,r);
		else if(v==3) ppt(ask1(rrt,0,mxn-2,l,r)),puts("");
		else ppt(ask2(rrt,0,mxn-2,l,r).st),puts("");
	}
}
  • 数组范围2~n+1,线段树范围0~200000,100pts,AC
int main(){
	rd(n),rd(m);
	for(ll i=2;i<=n+1;i++)
		rd(a[i]);
	bd(rrt,0,mxn-2);
	while(m--){
		ll v,l,r;
		rd(v),rd(l),rd(r);
		l+=2,r+=2;
		if(v<2) chg1(rrt,0,mxn-2,l,r,v);
		else if(v==2) chg2(rrt,0,mxn-2,l,r);
		else if(v==3) ppt(ask1(rrt,0,mxn-2,l,r)),puts("");
		else ppt(ask2(rrt,0,mxn-2,l,r).st),puts("");
	}
}
2021/8/15 09:45
加载中...