求助
查看原帖
求助
542879
_HCl_楼主2022/2/20 16:40

求助神佬告诉我我的代码哪有问题

#include<bits/stdc++.h>
using namespace std;
struct treeNode{
	int l,r;
	int sum;
	int tag,rev;
	int max[2],lmax[2],rmax[2];
};
int n,m;
treeNode tr[1000001];
int a[1000001];
void push_up(int p)
{
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	for(int i=0;i<=1;++i)
	{
		tr[p].lmax[i]=tr[p<<1].lmax[i];
		if(i==0)
		{
			if(tr[p<<1].sum==0)
			{
				tr[p].lmax[i]+=tr[p<<1|1].lmax[i];
			}
		}
		else
		{
			if(tr[p<<1].sum==tr[p<<1].r-tr[p<<1].l+1)
			{
				tr[p].lmax[i]+=tr[p<<1|1].rmax[i];
			}
		}
		tr[p].rmax[i]=tr[p<<1|1].rmax[i];
		if(i==0)
		{
			if(tr[p<<1|1].sum==0)
			{
				tr[p].rmax[i]+=tr[p<<1].rmax[i];
			}
		}
		else
		{
			if(tr[p<<1|1].sum==tr[p<<1|1].r-tr[p<<1|1].l+1)
			{
				tr[p].rmax[i]+=tr[p<<1].rmax[i];
			}
		}
		tr[p].max[i]=max(tr[p<<1].rmax[i]+tr[p<<1|1].lmax[i],max(tr[p<<1].max[i],tr[p<<1|1].max[i]));
	}
}
void build(int p,int l,int r)
{
	tr[p].l=l;
	tr[p].r=r;
	tr[p].tag=-1;
	if(l==r)
	{
		tr[p].sum=a[l];
		if(a[l]==0)
		{
			tr[p].max[0]=tr[p].lmax[0]=tr[p].rmax[0]=1;
		}
		else
		{
			tr[p].max[1]=tr[p].lmax[1]=tr[p].rmax[1]=1;
		}
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void push_down(int p)
{
	if(tr[p].tag!=-1)
	{
		tr[p].rev=0;
		int tag=tr[p].tag;
		tr[p<<1].sum=tag*(tr[p<<1].r-tr[p<<1].l+1);
		tr[p<<1|1].sum=tag*(tr[p<<1|1].r-tr[p<<1|1].l+1);
		tr[p<<1].max[tag]=tr[p<<1].lmax[tag]=tr[p<<1].rmax[tag]=tr[p<<1].r-tr[p<<1].l+1;
		tr[p<<1].max[tag^1]=tr[p<<1].lmax[tag^1]=tr[p<<1].rmax[tag^1]=0;
		tr[p<<1|1].max[tag]=tr[p<<1|1].lmax[tag]=tr[p<<1|1].rmax[tag]=tr[p<<1|1].r-tr[p<<1|1].l+1;
		tr[p<<1|1].max[tag^1]=tr[p<<1|1].lmax[tag^1]=tr[p<<1|1].rmax[tag^1]=0;
		tr[p<<1].tag=tr[p<<1|1].tag=tag;
		tr[p<<1].rev=tr[p<<1|1].rev=0;
		tr[p].tag=-1;
	}
	if(tr[p].rev)
	{
		tr[p<<1].sum=tr[p<<1].r-tr[p<<1].l+1-tr[p<<1].sum;
		tr[p<<1|1].sum=tr[p<<1|1].r-tr[p<<1|1].l+1-tr[p<<1|1].sum;
		if(tr[p<<1].tag!=-1)
		{
			tr[p<<1].tag^=1;
		}
		else
		{
			tr[p<<1].rev^=1;
		}
		if(tr[p<<1|1].tag!=-1)
		{
			tr[p<<1|1].tag^=1;
		}
		else
		{
			tr[p<<1|1].rev^=1;
		}
		swap(tr[p<<1].lmax[0],tr[p<<1].lmax[1]);
		swap(tr[p<<1].rmax[0],tr[p<<1].rmax[1]);
		swap(tr[p<<1].max[0],tr[p<<1].max[1]);
		swap(tr[p<<1|1].lmax[0],tr[p<<1|1].lmax[1]);
		swap(tr[p<<1|1].rmax[0],tr[p<<1|1].rmax[1]);
		swap(tr[p<<1|1].max[0],tr[p<<1|1].max[1]);
		tr[p].rev=0;
	}
}
void update(int p,int op,int l,int r)
{
	push_down(p);
	if(tr[p].l==l&&tr[p].r==r)
	{
		if(op==0||op==1)
		{
			tr[p].sum=op*(tr[p].r-tr[p].l+1);
			tr[p].max[op]=tr[p].lmax[op]=tr[p].rmax[op]=tr[p].r-tr[p].l+1;
			tr[p].max[op^1]=tr[p].lmax[op^1]=tr[p].rmax[op^1]=0;
			tr[p].tag=op;
		}
		else if(op==2)
		{
			tr[p].sum=tr[p].r-tr[p].l+1-tr[p].sum;
			tr[p].rev^=1;
			swap(tr[p].lmax[0],tr[p].lmax[1]);
			swap(tr[p].rmax[0],tr[p].rmax[1]);
			swap(tr[p].max[0],tr[p].max[1]);
		}
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(mid<l)
	{
		update(p<<1|1,op,l,r);
	}
	else if(mid>=r)
	{
		update(p<<1,op,l,r);
	}
	else
	{
		update(p<<1,op,l,mid);
		update(p<<1|1,op,mid+1,r);
	}
	push_up(p);
}
int getSum(int p,int l,int r)
{
	push_down(p);
	if(tr[p].l==l&&tr[p].r==r)
	{
		return tr[p].sum;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(mid<l)
	{
		return getSum(p<<1|1,l,r);
	}
	else if(mid>=r)
	{
		return getSum(p<<1,l,r);
	}
	else
	{
		return getSum(p<<1,l,mid)+getSum(p<<1|1,mid+1,r);
	}
}
treeNode getMax(int p,int l,int r)
{
	push_down(p);
	if(tr[p].l==l&&tr[p].r==r)
	{
		return tr[p];
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(mid<l)
	{
		return getMax(p<<1|1,l,r);
	}
	else if(mid>=r)
	{
		return getMax(p<<1,l,r);
	}
	else
	{
		treeNode ans;
		treeNode lc=getMax(p<<1,l,mid);
		treeNode rc=getMax(p<<1|1,mid+1,r);
		ans.sum=lc.sum+rc.sum;
		for(int i=0;i<=1;++i)
		{
			ans.lmax[i]=lc.lmax[i];
			if(i==0)
			{
				if(lc.sum==0)
				{
					ans.lmax[i]+=rc.lmax[i];
				}
			}
			else
			{
				if(lc.sum==lc.r-lc.l+1)
				{
					ans.lmax[i]+=rc.lmax[i];
				}
			}
			ans.rmax[i]=rc.rmax[i];
			if(i==0)
			{
				if(rc.sum==0)
				{
					ans.rmax[i]+=lc.rmax[i];
				}
			}
			else
			{
				if(rc.sum==rc.r-rc.l+1)
				{
					ans.rmax[i]+=lc.rmax[i];
				}
			}
			ans.max[i]=max(lc.rmax[i]+rc.lmax[i],max(lc.max[i],rc.max[i]));
		}
		return ans;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		int op,l,r;
		cin>>op>>l>>r;
		++l;
		++r;
		if(op==0)
		{
			update(1,0,l,r);
		}
		else if(op==1)
		{
			update(1,1,l,r);
		}
		else if(op==2)
		{
			update(1,2,l,r);
		}
		else if(op==3)
		{
			cout<<getSum(1,l,r)<<endl;
		}
		else
		{
			cout<<getMax(1,l,r).max[1]<<endl;
		}
	}
}
2022/2/20 16:40
加载中...