萌新求助线段树入门题
查看原帖
萌新求助线段树入门题
222104
_yjh楼主2021/10/7 19:48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
	ll sum,lx,rx,sx,size;
}Node[4*200005]; 
ll n,m,sum,a[200005],lazy[4*200005];
node no;
void UP(ll t) {
	Node[t].sum=Node[2*t].sum+Node[2*t+1].sum;
	Node[t].sx=max(max(Node[2*t].sx,Node[2*t+1].sx),Node[2*t].rx+Node[2*t+1].lx);
	if(Node[2*t].sum==Node[2*t].size) Node[t].lx=Node[2*t].size+Node[2*t+1].lx;
	else Node[t].lx=Node[2*t].lx;
	if(Node[2*t+1].sum==Node[2*t+1].size) Node[t].rx=Node[2*t+1].size+Node[2*t].rx;
	else Node[t].rx=Node[2*t+1].rx;
	Node[t].size=Node[2*t].size+Node[2*t+1].size;
}  
void Push(int t,int len) {
	if(!lazy[t]) return ;
	if(lazy[t]==1) { //更0 
		Node[2*t].sum=len-len/2;
		Node[2*t].lx=Node[2*t].rx=Node[2*t].sx=(len-len/2);
		lazy[2*t]=1;
		Node[2*t+1].sum=len/2;
		Node[2*t+1].lx=Node[2*t+1].rx=Node[2*t+1].sx=len/2;
		lazy[2*t+1]=1;
		lazy[t]=0;
	}
	else { //更1 
		Node[2*t].sum=0;
		Node[2*t].lx=Node[2*t].rx=Node[2*t].sx=0;
		lazy[2*t]=-1;
		Node[2*t+1].sum=0;
		Node[2*t+1].lx=Node[2*t+1].rx=Node[2*t+1].sx=0;
		lazy[2*t+1]=-1;
		lazy[t]=0;
	}
}
void Build(int t,int l,int r) {
	if(l==r) {
		Node[t].sum=!a[l];
		Node[t].lx=Node[t].rx=Node[t].sx=!a[l];
		Node[t].size=1;
		return ;
	}
	int mid=(l+r)/2;
	Build(2*t,l,mid);
	Build(2*t+1,mid+1,r);
	UP(t);
}
void Query(int t,int l,int r,int ll,int rr) {
	if(ll<=l&&r<=rr) {
		if(no.sum==-1&&no.lx==-1&&no.rx==-1&&no.sx==-1&&no.size==-1) no=Node[t];
		else { //个人认为符合特殊性质?即拆分后区间计算顺序是从左往右的 
			node _no=no;
			no.size+=Node[t].size;
			no.sum=_no.sum+Node[t].sum;
        	no.sx=max(max(_no.sx,Node[t].sx),_no.rx+Node[t].lx);
        	if(_no.sum==_no.size) no.lx=_no.size+Node[t].lx;
         	else no.lx=_no.lx;
        	if(Node[t].sum==Node[t].size) no.rx=Node[t].size+_no.rx;
        	else no.rx=Node[t].rx;
		}
		return ;
	}
	Push(t,r-l+1);
	int mid=(l+r)/2;
	if(ll<=mid) Query(2*t,l,mid,ll,rr);
	if(rr>=mid+1) Query(2*t+1,mid+1,r,ll,rr);
}
void Change(int t,int l,int r,int ll,int rr,int to) {
	if(ll<=l&&r<=rr) {
		if(to==0) {
			Node[t].sum=r-l+1;
		    Node[t].lx=Node[t].rx=Node[t].sx=Node[t].size;
		    lazy[t]=1;
		}
		else {
			Node[t].sum=0;
	    	Node[t].lx=Node[t].rx=Node[t].sx=0;
	    	lazy[t]=-1;
		}
		return ;
	}
	Push(t,r-l+1);
	int mid=(l+r)/2;
	if(ll<=mid) Change(2*t,l,mid,ll,rr,to);
	if(rr>=mid+1) Change(2*t+1,mid+1,r,ll,rr,to);
	UP(t);
}
int main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) a[i]=1;
	Build(1,1,n);
	while(m--) {
		ll t,l,r,lt,rt;
		scanf("%lld",&t);
		if(t==0) {
			scanf("%lld%lld",&l,&r);
			Change(1,1,n,l,r,0);
		}
		if(t==1) {
			scanf("%lld%lld%lld%lld",&l,&r,&lt,&rt);
			no=(node){-1,-1,-1,-1,-1};
			Query(1,1,n,l,r);
			ll num=no.size-no.sum;
			no=(node){-1,-1,-1,-1,-1};
			Query(1,1,n,lt,rt);
			if(num>=no.sum) Change(1,1,n,lt,rt,1);
			else {
				ll fnum=no.sum;
				ll _l=lt,_r=rt,ans;
				while(_l<=_r) {
					ll mid=(_l+_r)/2;
					no=(node){-1,-1,-1,-1,-1};
			        Query(1,1,n,lt,mid);
			        if(no.sum<=num) ans=mid,_l=mid+1;
			        else _r=mid-1;
				}
		        Change(1,1,n,lt,ans,1);
			}
			Change(1,1,n,l,r,0);
		}
		if(t==2) {
			scanf("%lld%lld",&l,&r);
			no=(node){-1,-1,-1,-1,-1};
			Query(1,1,n,l,r);
			printf("%lld\n",no.sx);
		}
	}
	return 0;
} 

原来5pts,调了0.5h变成10pts。

实在找不出明显错误了,求查错,谢谢。(代码有看不懂的地方可以问我)

2021/10/7 19:48
加载中...