求助,动态开点线段树不知道错在哪里,WA了,求大佬指点
查看原帖
求助,动态开点线段树不知道错在哪里,WA了,求大佬指点
316681
zhongshizhao1楼主2023/6/29 16:24
#include <bits/stdc++.h>
using namespace std;
int tot=1;
struct node
{
	long long sum;//从左开始1的个数 
	long long sum2;//从左开始0的个数 
	int tag1,tag2;
	int lson,rson;
}tree[20000005];
void pushup(int id,long long nl,long long nr,long long mid,int a1,int a2)
{
	tree[id].sum=tree[a1].sum;
	tree[id].sum2=tree[a1].sum2;
	if(tree[a1].sum==mid-nl+1)
	{
		tree[id].sum=tree[a1].sum+tree[a2].sum;
	}
	if(tree[a1].sum2==mid-nl+1)
	{
		tree[id].sum2=tree[a1].sum2+tree[a2].sum2;
	}
}
void pushdown(int id,long long nl,long long nr,long long mid)
{
	if(tree[id].lson==0)
	{
		tot++;
		tree[tot].sum2=mid-nl+1;
		tree[id].lson=tot;
		tot++;
		tree[tot].sum2=nr-mid;
		tree[id].rson=tot;
	}
	int a1=tree[id].lson;
	int a2=tree[id].rson;
	if(tree[id].tag1==1)
	{
		tree[id].tag1=0;
		tree[a1].tag1=1;
		tree[a2].tag1=1;
		tree[a1].tag2=0;
		tree[a2].tag2=0;
		tree[a1].sum=mid-nl+1;
		tree[a2].sum=nr-mid;
		tree[a1].sum2=tree[a2].sum2=0;
	}
	else if(tree[id].tag1==-1)
	{
		tree[id].tag1=0;
		tree[a1].tag1=-1;
		tree[a2].tag1=-1;
		tree[a1].tag2=0;
		tree[a2].tag2=0;
		tree[a1].sum=tree[a2].sum=0;
		tree[a1].sum2=mid-nl+1;
		tree[a2].sum2=nr-mid;
	}
	if(tree[id].tag2==1)
	{
		tree[id].tag2=0;
		swap(tree[a1].sum,tree[a1].sum2);
		swap(tree[a2].sum,tree[a2].sum2);
		tree[a1].tag2=1;
		tree[a2].tag2=1;
	}
}
void update1(int id,long long nl,long long nr,long long l,long long r)
{
	if(nl>=l&&nr<=r)
	{
		tree[id].sum=nr-nl+1;
		tree[id].sum2=0; 
		tree[id].tag1=1;
		tree[id].tag2=0;
		return;
	}
	long long mid=(nl+nr)>>1;
	pushdown(id,nl,nr,mid);
	if(mid>=l)update1(tree[id].lson,nl,mid,l,r);
	if(mid<r)update1(tree[id].rson,mid+1,nr,l,r);
	pushup(id,nl,nr,mid,tree[id].lson,tree[id].rson);
}
void update2(int id,long long nl,long long nr,long long l,long long r)
{
	if(nl>=l&&nr<=r)
	{
		tree[id].sum=0;
		tree[id].sum2=nr-nl+1;
		tree[id].tag1=-1;
		tree[id].tag2=0;
		return;
	}
	long long mid=(nl+nr)>>1;
	pushdown(id,nl,nr,mid);
	if(mid>=l)update2(tree[id].lson,nl,mid,l,r);
	if(mid<r)update2(tree[id].rson,mid+1,nr,l,r);
	pushup(id,nl,nr,mid,tree[id].lson,tree[id].rson);
}
void update3(int id,long long nl,long long nr,long long l,long long r)
{
	if(nl>=l&&nr<=r)
	{
		swap(tree[id].sum,tree[id].sum2);
		if(tree[id].tag2==1)tree[id].tag2=0;
		else tree[id].tag2=1;
		return;
	}
	long long mid=(nl+nr)>>1;
	pushdown(id,nl,nr,mid);
	if(mid>=l)update3(tree[id].lson,nl,mid,l,r);
	if(mid<r)update3(tree[id].rson,mid+1,nr,l,r);
	pushup(id,nl,nr,mid,tree[id].lson,tree[id].rson);
}
int main()
{
	int q;
	cin>>q;
	int t;
	long long x,y;
	tree[1].sum2=1000000000000000000;
	for(int i=1;i<=q;i++)
	{
		cin>>t>>x>>y;
		if(t==1)
		{
			update1(1,1,1000000000000000000,x,y);	
		} 
		else if(t==2)
		{
			update2(1,1,1000000000000000000,x,y);
		}
		else
		{
			update3(1,1,1000000000000000000,x,y);
		}
		cout<<tree[1].sum+1<<'\n';
	}
	return 0;
}
2023/6/29 16:24
加载中...