结构体线段树,到底是哪里错了?有注释
查看原帖
结构体线段树,到底是哪里错了?有注释
551894
lemon2021楼主2023/2/7 21:23

结构体线段树,到底是哪里错了?请大佬们帮忙看看

#include<iostream>
using namespace std;
const long long MAXN=200001;
struct node
{
	long long l;//左儿子 
	long long r;//右儿子 
	long long sum;//叶子节点和 
	long long lazy;//懒惰标记
	node(){l=r=sum=lazy=0;}//初始为0 
}a[MAXN<<2];//树 
void update(long long x)//更新叶子节点和 
{
	a[x].sum=a[x*2].sum+a[x*2+1].sum;
}
void buildtree(long long x,long long l,long long r)//建树 
{
	a[x].l=l,a[x].r=r;
	if(l==r)
	{
		return;
	}
	long long mid=(l+r)/2;
	buildtree(x*2,l,mid);
	buildtree(x*2+1,mid+1,r);
}
void pushdown(long long x)//将点x的懒惰标记下传
{
	if(a[x].sum==0)
	{
		return;
	}
	if(a[x].l==a[x].r)
	{
		a[x].lazy=0;
		return;
	}
	a[x*2].sum+=(a[x*2].r-a[x*2].l+1)*a[x].lazy;
	a[x*2+1].sum+=(a[x*2+1].r-a[x*2+1].l+1)*a[x].lazy;
	a[x*2].lazy+=a[x].lazy;
	a[x*2+1].lazy+=a[x].lazy;
	a[x].lazy=0;
}
void changesegment(long long x,long long l,long long r)//区间取反
{
	pushdown(x);
	if(a[x].l==l&&a[x].r==r)
	{
		a[x].sum+=r-l+1-a[x].sum;//取反 
		a[x].lazy=1;//懒惰标记
		return;
	}
	long long mid=(a[x].l+a[x].r)/2;
	if(r<=mid)
	{
		changesegment(x*2,l,r);
	}
	else
	{
		if(l>mid)
		{
			changesegment(x*2+1,l,r);
		}
		else
		{
			changesegment(x*2,l,mid);
			changesegment(x*2+1,mid+1,r);
		}
	}
	update(x);
}
long long querysum(long long x,long long l,long long r)//区间求和
{
	pushdown(x);
	if(a[x].l==l&&a[x].r==r)
	{
		return a[x].sum;
	}
	long long mid=(a[x].l+a[x].r)/2;
	if(r<=mid)
	{
		return querysum(x*2,l,r);
	}
	if(l>mid)
	{
		return querysum(x*2+1,l,r);
	}
	return querysum(x*2,l,mid)+querysum(x*2+1,mid+1,r);
}
int main()
{
	long long n,m;//n为元素个数,m为操作次数 
	cin>>n>>m;
	buildtree(1,1,n);//建树 
	for(long long i=1;i<=m;i++)
	{
		long long t,l,r;
		cin>>t;
		if(t==0)
		{
			cin>>l>>r;
			changesegment(1,l,r);
		}
		if(t==1)
		{
			cin>>l>>r;
			cout<<querysum(1,l,r)<<endl;
		}
	}
	return 0;
}
2023/2/7 21:23
加载中...