自动搬运

查看原文

来自洛谷，原作者为

	TainityAnle My excellence is undeniable!

搬运于2025-08-24 21:17:10，当前版本为作者最后更新于2024-12-26 18:46:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

全场最劣解祭。

题意

给定一个初始为 $0$ 的序列，每次可以将它的一个区间 01 翻转，问这个区间的最终结果。

思路

容易发现一个点被翻奇数次就会变成 $1$，翻偶数次就会变成 $0$。所以我们只需要统计每个点被翻转的次数。

每次翻转一个区间，可以用区间加，但是线段树的代码过于复杂，会吓到小学组的孩子们，我选择使用优化后的暴力。

我们可以给这个区间分成若干个长度为 $\sqrt{n}$ 的块。对于每次修改的区间可以被分为三部分：中间的整块，左边不足一块的和右边不足一块的部分。

对于中间的整块，给每一个块打上一个加 $1$ 的标记，对于两遍不足一块的部分，直接暴力加就好了。发现中间块的个数不会超过 $\sqrt{n}$，两遍的长度分别不会超过 $\sqrt{n}$，所以总体一次修改就是 $O(\sqrt{n})$ 的。

查询的时候，只需要将每个点所在块的加 $1$ 标记数和暴力加的次数加起来即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,pos[200050],len,a[200005],b[500],L[500],R[500];//a是每个数暴力加的次数，b是每个块的标记 
void add(int l,int r){
	int p=pos[l],q=pos[r];
	if(p==q){//特判修改端点在一个块的情况 
		for(int i=l;i<=r;i++) a[i]++;
		return;
	}
	for(int i=l;i<=R[p];i++) a[i]++;//处理左边散块 
	for(int i=L[q];i<=r;i++) a[i]++; //处理右边散块 
	for(int i=p+1;i<=q-1;i++) b[i]++; //处理整块 
}
int main(){
	cin>>n>>m;
	len=sqrt(n);
	for(int i=1;i<=len;i++){
		L[i]=(i-1)*sqrt(n)+1;
		R[i]=i*sqrt(n);
	}
	if(R[len]<n){
		len++;
		L[len]=R[len-1]+1,R[len]=n;
	}
	for(int i=1;i<=len;i++)
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i;
	//以上是分块预处理，维护每个块左、右端点，每个点属于哪个块 
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++) {
		int val=a[i]+b[pos[i]];
		cout<<(val&1);
	}
	return 0;
}

这份代码以 $O(n\sqrt n)$ 的时间复杂度成功地成为了本题 AC 记录中最慢的一个，10 个点共耗时 600ms。