线段树求调
查看原帖
线段树求调
523541
Onana_in_XMFLS楼主2023/7/1 15:57
// Problem: P3870 [TJOI2009] 开关
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3870
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define mem(arr,val) memset((arr),(val),(sizeof(arr)))
using namespace std;
const int maxn = 1e5+5;
struct tree
{
	int sum,lazy;
}tr[maxn*4];
int n,m;
void pushup(int x) {tr[x].sum = tr[x*2].sum+tr[x*2+1].sum;}
void pushdown(int x,int l,int r)
{
	if(!tr[x].lazy) return;
	int mid = (l+r)/2;
	tr[x*2].sum = mid-l+1-tr[x*2].sum;
	tr[x*2].lazy ^= 1;
	tr[x*2+1].sum = r-mid-tr[x*2+1].sum;
	tr[x*2+1].lazy ^= 1;
	tr[x].lazy = 0;
}
void update(int l,int r,int lnow,int rnow,int x)
{
	if(l <= lnow && rnow <= r)
	{
		tr[x].sum = r-l+1-tr[x].sum;
		tr[x].lazy ^= 1;
	}
	else
	{
		int mid = (lnow+rnow)/2;
		pushdown(x,lnow,rnow);
		if(l <= mid) update(l,r,lnow,mid,x*2);
		if(mid < r) update(l,r,mid+1,rnow,x*2+1);
		pushup(x);
	}		
}
int query(int l,int r,int lnow,int rnow,int x)
{
	if(l <= lnow && rnow <= r) return tr[x].sum;
	int mid = (lnow+rnow)/2,a = 0,b = 0;
	pushdown(x,lnow,rnow);
	if(l <= mid) a = query(l,r,lnow,mid,x*2);
	if(mid < r) b = query(l,r,mid+1,rnow,x*2+1);
	return a+b;
}
int main(int argc,char *argv[])
{
	scanf("%d%d",&n,&m);
	build(1,n,1);
	while(m--)
	{
		int c,a,b;scanf("%d%d%d",&c,&a,&b);
		if(c) printf("%d\n",query(a,b,1,n,1));
		else update(a,b,1,n,1);
	}
	return 0;
}
2023/7/1 15:57
加载中...