警示后人,如果你分块10pts
查看原帖
警示后人,如果你分块10pts
439609
封禁用户楼主2024/11/26 19:32

记得在还原懒标记时不要更改ans数组,如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,fk[N],a[N],c,aa,b,len,ans[N];
bool tag[N];
int ls(int x)
{
	return (x-1)*len+1;
}
int rs(int x)
{
	return x*len;
}
void Change(int x)
{
	for(int i=ls(x);i<=rs(x);i++) a[i]=!a[i];
	ans[x]=len-ans[x];//这行应删去 
	tag[x]=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	len=sqrt(n);
	for(int i=1;i<=n;i++) fk[i]=(i-1)/len+1;
	while(m--)
	{
		scanf("%d%d%d",&c,&aa,&b);
		int xa=fk[aa],xb=fk[b],zh=0;
		if(tag[xa]) Change(xa);
		if(tag[xb]) Change(xb);
		if(!c)
		{
			if(xa==xb)
			{
				for(int i=aa;i<=b;i++)
				{
					if(a[i]) ans[xa]--;
					else ans[xa]++;
					a[i]=!a[i];
				}
				continue;
			}
			for(int i=xa+1;i<xb;i++)
			{
				ans[i]=len-ans[i];
				tag[i]=!tag[i];
			}
			for(int i=aa;i<=rs(xa);i++)
			{
				if(a[i]) ans[xa]--;
				else ans[xa]++;
				a[i]=!a[i];
			}
			for(int i=ls(xb);i<=b;i++)
			{
				if(a[i]) ans[xb]--;
				else ans[xb]++;
				a[i]=!a[i];
			}
		}
		else
		{
			if(xa==xb)
			{
				for(int i=aa;i<=b;i++) zh+=a[i];
				printf("%d\n",zh);
				continue;
			}
			for(int i=xa+1;i<xb;i++) zh+=ans[i];
			for(int i=aa;i<=rs(xa);i++) zh+=a[i];
			for(int i=ls(xb);i<=b;i++) zh+=a[i];
			printf("%d\n",zh);
		}
	}
	return 0;
}
2024/11/26 19:32
加载中...