线段树20pts求条
查看原帖
线段树20pts求条
982518
sjwhsss楼主2024/8/15 22:03

rt,看过讨论区了,没发现问题

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+5;
int n , q , t[maxn<<2];
bool tag[maxn];
inline int input()
{
	char ch=getchar();int x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
inline void print(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+48);
}
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
void PushUp(int p){t[p]=t[ls(p)]+t[rs(p)];}
void PushDown(int p , int l , int r)
{
	if(tag[p])
	{
		int mid = l + r >> 1;
		t[ls(p)]=mid - l + 1 - t[ls(p)];
		t[rs(p)]=r - mid - t[rs(p)];
		tag[ls(p)]^=1;
		tag[rs(p)]^=1;
		tag[p]=0;
	}
	return;
}
void Build(int p , int l , int r)
{
	if (l == r)return;
	int mid = l + r >> 1;
	Build(ls(p) , l , mid);
	Build(rs(p) , mid + 1 , r);
	PushUp(p);
	return;
}
void Update(int p , int l , int r , int L , int R)
{
	//cout << p << ' ' << l << " " << r << ' ' << L << " " << R << endl;
	if (L <= l && r <= R){t[p]=r - l + 1 - t[p],tag[p]^=1;return;}
	PushDown(p , l , r);
	int mid = l + r >> 1;
	if (L <= mid) Update(ls(p) , l , mid , L , R);
	if (R > mid) Update(rs(p) , mid + 1 , r , L , R);
	PushUp(p);
	return;
}
int Query(int p , int l , int r , int L , int R)
{
	if (L <= l && r <= R)return t[p];
	PushDown(p , l , r);
	int mid = l + r >> 1;
	int res = 0;
	if (L <= mid) res+=Query(ls(p) , l , mid , L , R);
	if (R > mid) res+=Query(rs(p) , mid + 1 , r , L , R);
	return res;
}
main ()
{
	n=input(),q=input();
	Build(1 , 1 , n);
	//cout << n << " " << q;return 0;
	//cout << Query(1 , 1 , n , 1 , n);return 0;
	while(q--)
	{
		int op=input() , a=input() , b=input();
		//cout << op << " " << a << " " << b << endl;
		//cout << Query(1 , 1 , n , 1 , n) << endl;
		if (!op)Update(1 , 1 , n , a , b);
		else print(Query(1 , 1 , n , a , b)),putchar('\n');
		
	}
	return 0;
}
2024/8/15 22:03
加载中...