自动搬运

查看原文

来自洛谷，原作者为

	Shadow_T 控制自己的言行

搬运于2025-08-24 22:56:47，当前版本为作者最后更新于2024-04-11 20:35:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

一开始有一个序列 $a$，有 $q$ 次修改，每次可以修改一个值。对于每次修改后你需要输出此时的 $a$ 进行以下操作若干次的循环节最小长度：

• 将每个元素 $a_i$ 替换为 $\bigoplus\limits_{j=1}^ia_j$。

题目分析

首先，我们发现，对于第 $i$ 个元素，它会把前面的元素的组合都出现一遍，那么 $a_i$ 肯定 $2^{\lceil \log_2 i \rceil}$ 循环一次。对于长度为 $n$ 的序列，循环节就是所有 $a_i$ 循环节的最小公倍数，由于都是 $2$ 的整数次方，所以为 $2^{\lceil \log_2 n \rceil}$。

但是很明显，有一段是特殊的，即 $a$ 的前导 $0$，不管迭代其次也不会改变自身，不会影响后面的东西。

然后我们要维护动态前导 $0$，很多人暴力维护赛时过了，这里已经 hack 掉了（第 $7$ 个点）。This。

其实这个动态前导 $0$ 类似一个动态 $\operatorname{mex}$，可以用 set 维护。详见 Link 的 set 部分。

时间复杂度 $\mathcal{O}(n\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int a[maxn];
int main()
{
	int n,q;
	cin>>n>>q;
	set<int> s;
	for(int i=1;i<=n+1;i++)
	s.insert(i);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]==0) s.erase(s.lower_bound(i));
	}
	while(q--)
	{
		int x,z;
		scanf("%d%d",&x,&z);
		if(a[x]!=0&&z==0) s.erase(s.lower_bound(x));
		else
		{
			if(a[x]==0&&z!=0)
			s.insert(x);
		}
		a[x]=z;
		int y=n-*s.begin()+1;
		int ans=1;
		while(ans<y) ans*=2;
		cout<<ans<<"\n";
	}
}