欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷—P3870 开关(线段树入门)

程序员文章站 2022-07-14 08:31:15
...

洛谷—P3870 开关(线段树入门)
此处应该注意lazy的维护,即lazy的值应该是在1-0之间翻转的,其他没问题

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
#define ll long long
ll sum[maxn<<2],tag[maxn<<2];
void pushdown(int p,int l,int r)
{
	if(tag[p])
	{
		int mid=(l+r)>>1;
		tag[p<<1]^=1;
		tag[p<<1|1]^=1;
		sum[p<<1]=(mid-l+1)-sum[p<<1];
		sum[p<<1|1]=(r-mid)-sum[p<<1|1];
		tag[p]=0;
	} 
}
void pushup(int p,int l,int r)
{
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
void change(int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&qr>=r)
	{
		tag[p]^=1;
		sum[p]=(r-l+1)-sum[p];
		return;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) change(p<<1,l,mid,ql,qr);
	if(qr>mid) change(p<<1|1,mid+1,r,ql,qr);
	pushup(p,l,r);
}
ll query(int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&qr>=r) return sum[p];
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	ll res=0;
	if(ql<=mid) res+=query(p<<1,l,mid,ql,qr);
	if(qr>mid) res+=query(p<<1|1,mid+1,r,ql,qr);
	return res;
}
int main()
{
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int temp,x,y;
		cin>>temp>>x>>y;
		if(temp==0) change(1,1,n,x,y);
		else cout<<query(1,1,n,x,y)<<endl;
	}
	return 0;
}
相关标签: 线段树