社区讨论

大佬求助,蒟蒻线段树10分

P3870[TJOI2009] 开关参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi7xsobr
此快照首次捕获于
2025/11/21 05:22
4 个月前
此快照最后确认于
2025/11/21 05:22
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
using namespace std;
struct node
{
	int l,r;
	int w;
	int lazy;
	node()
	{
		w=0; lazy=0;
	} 
};
node tree[100001<<2];
int n,m,ans=0;
void build(int k,int l,int r);
void pushdown(int k);
void update(int k,int a,int b);
void ask(int k,int a,int b);
int main()
{
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int step,a,b;
		scanf("%d %d %d",&step,&a,&b);
		if(step==0) update(1,a,b);
		else
		{
			ans=0;
			ask(1,a,b);
			printf("%d\n",ans);
		}
	}
	return 0;
}
void build(int k,int l,int r)
{
	tree[k].l=l; tree[k].r=r;
	if(l==r)
	{
		tree[k].w=0;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
	return;
}
void update(int k,int a,int b)
{
	if(a<=tree[k].l && tree[k].r<=b)
	{
		tree[k].w=(tree[k].r-tree[k].l+1)-tree[k].w;
		if(tree[k].lazy) tree[k].lazy=0;
		else tree[k].lazy=1;
//		if(tree[k].lazy) pushdown(k);
		return;
	}
	if(tree[k].lazy) pushdown(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(a<=mid) update(k<<1,a,b);
	if(b>mid) update(k<<1|1,a,b);
	tree[k].w=tree[k<<1].w+tree[k<<1|1].w; 
}
void pushdown(int k)
{
	tree[k<<1].w=tree[k<<1].r-tree[k<<1].l+1-tree[k<<1].w;
	tree[k<<1].lazy=1;
	tree[k<<1|1].w=tree[k<<1|1].r-tree[k<<1|1].l+1-tree[k<<1|1].w;
	tree[k<<1|1].lazy=1;
	tree[k].lazy=0;
	return;
}
void ask(int k,int a,int b)
{
	if(a<=tree[k].l && tree[k].r<=b)
	{
		ans+=tree[k].w;
		return;
	}
	if(tree[k].lazy) pushdown(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(a<=mid) ask(k<<1,a,b);
	if(b>mid) ask(k<<1|1,a,b);
}

回复

4 条回复,欢迎继续交流。

正在加载回复...