十分分块蒟蒻求助QwQ
查看原帖
十分分块蒟蒻求助QwQ
233957
190040257a楼主2020/8/11 21:42

感觉这题挺简单的,就是不知道哪里错了QwQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[203000];
int N,M;
int bel[50000];
int rag[50000];
int sum[50000];
int sq;
int Change(int l,int r)
{
	for(int i=l;i<=min(bel[l]*sq,r);i++)
	{
		rag[bel[i]]-=a[i];
		a[i]=!a[i];
		rag[bel[i]]+=a[i];
	}
	if(bel[l]!=bel[r])
	{
		for(int i=(bel[r]-1)*sq+1;i<=r;i++)
		{
			rag[bel[i]]-=a[i];
			a[i]=!a[i];
			rag[bel[i]]+=a[i];
		}
	}//碎块 
	for(int i=bel[l]+1;i<bel[r];i++)
	{
		rag[i]=(sq-rag[i])*1;
		sum[i]+=1;
	}
}//处理操作 
int search(int l,int r)
{
	int s=0;
	for(int i=l;i<=min(r,bel[l]*sq);i++)
	{
		s+=a[i]*1;
	}
	if(bel[l]!=bel[r])
	{
		for(int i=(bel[r]-1)*sq+1;i<=r;i++)
		{
			s+=a[i]*1;
		}
	}//碎块 
	for(int i=bel[l]+1;i<bel[r];i++)
	{
		s+=rag[i];
	}
	return s;
}//查询操作 
int main()
{
	cin>>N>>M;
	sq=sqrt(N);
	for(int i=1;i<=N;i++)
	{
		a[i]=0;
		bel[i]=(i-1)/sq+1;
	}
	for(int i=1;i<=M;i++)
	{
		int z,l,r;
		cin>>z>>l>>r;
		if(z==0)
		{
			Change(l,r);
		}
		if(z==1)
		{
			cout<<search(l,r)<<endl;
		}
	}
	return 0;
}
2020/8/11 21:42
加载中...