10pts 样例和自己造的数据都过了求调
查看原帖
10pts 样例和自己造的数据都过了求调
776799
GODTREE楼主2025/6/30 11:40
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n,m;
struct tree
{
	int cnt,l,r,lz;
}t[N*4];
void build(int u,int l,int r)
{
	t[u].l=l;
	t[u].r=r;
	if (l==r)
	{
		t[u].cnt=0;
		return ;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	t[u].cnt=t[u*2].cnt+t[u*2+1].cnt;
}
void push_down(int u)
{
	t[u].cnt=t[u].r-t[u].l+1-t[u].cnt;
	t[u].lz=1;
}
void change(int u,int l,int r)
{
	if (t[u].r<l||t[u].l>r)
	{
		return ;
	}
	if (t[u].l>=l&&t[u].r<=r)
	{
		t[u].cnt=t[u].r-t[u].l+1-t[u].cnt;
		t[u].lz++;
		return ;
	}
	if (t[u].lz%2==1)
	{
		t[u].lz=0;
		push_down(u*2);
		push_down(u*2+1);
	}
	change(u*2,l,r);
	change(u*2+1,l,r);
	t[u].cnt=t[u*2].cnt+t[u*2+1].cnt;
}
int query(int u,int l,int r)
{
	if (t[u].r<l||t[u].l>r)
	{
		return 0;
	}
	if (t[u].l>=l&&t[u].r<=r)
	{
		return t[u].cnt;
	}
	if (t[u].lz%2==1)
	{
		t[u].lz=0;
		push_down(u*2);
		push_down(u*2+1);
	}
	return query(u*2,l,r)+query(u*2+1,l,r);
}
int main()
{
	cin>>n>>m;
	build(1,1,n);
	for (int i=1;i<=m;i++)
	{
		int opt,l,r;
		cin>>opt>>l>>r;
		if (opt==0)
		{
			change(1,l,r);
		}
		else 
		{
			cout<<query(1,l,r)<<"\n";
		}
	}
	return 0;
}
2025/6/30 11:40
加载中...