线段树求条玄关
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/7/23 09:05
  • 上次更新2024/7/23 10:06:20
查看原帖
线段树求条玄关
745358
ChenZQ楼主2024/7/23 09:05

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int seg[N<<2],tag[N<<2];
int n,m;

void pd(int u,int l,int r)
{
	int m=(l+r)>>1;
	if(tag[u]%2==1)
	{
		seg[u<<1]=m-l+1-seg[u<<1];
		seg[u<<1|1]=r-m-seg[u<<1|1];
		tag[u<<1]+=tag[u];
		tag[u<<1|1]+=tag[u];
	}
	tag[u]=0;
}
void update(int l,int r,int ll,int rr,int u)
{
	if(l>=ll && r<=rr) 
	{
		seg[u]=r-l+1-seg[u];
		tag[u]++;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ll) update(l,mid,ll,rr,u<<1);
	if(mid<rr) update(mid+1,r,ll,rr,u<<1|1);
	seg[u]=seg[u<<1]+seg[u<<1|1];
	
}
int query(int l,int r,int ll,int rr,int u)
{
	if(l!=r) pd(u,l,r);
	if(l>=ll && r<=rr) return seg[u];
	int mid=(l+r)>>1;
	int k=0;
	if(mid>=ll) k+=query(l,mid,ll,rr,u<<1);
	if(mid<rr) k+=query(mid+1,r,ll,rr,u<<1|1);
	return k;
}

int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1) printf("%d\n",query(1,n,x,y,1));
		else update(1,n,x,y,1);
	}
} 
2024/7/23 09:05
加载中...