自动搬运

查看原文

来自洛谷，原作者为

	a___ 这个家伙很蒻，什么也没有留下qwq

搬运于2025-08-24 22:28:59，当前版本为作者最后更新于2021-03-29 18:27:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，由于修改复杂度较大，所以我们考虑修改打 tag，查询时再求具体值。开一个数组 $b$ 记录 $ki,k\in Z^+$ 的位置都异或了 $b_i$；查询的时候枚举下标的所有因数 $p$，异或上所有的 $b_p$ 即可。

然后我们对于所有 $3$、$4$ 操作，暴力修改。于是就拿到了 $68$ 分。

全部的部分分！

考虑 $3$ 操作。发现由于 $[u,i)$ 一定没有 $3$、$4$ 操作，所以每个 $1$、$2$ 操作只会最多被一个 $3$ 操作覆盖，所以在没有 $4$ 操作的情况下暴力询问数是 $\mathbf O(n)$ 的。

考虑 $4$ 操作。这里定义一个 $4$ 操作 $i$ 的对应操作为不断跳 $i=x_i$ ，直到 $op_i\not=4$ 的第一个 $i$。分类讨论：

如果对应操作是 $1$ 或 $2$，那么直接暴力修改，没啥说的。

否则，由于 $(x,i)$ 一定没有 $3$、$4$，那么最劣情况为，一个 $4\to4\to4\to\dots\to3$，于是一个 $3$ 操作被反复执行了很多次，复杂度爆炸。

然鹅由于这题修改是异或，所以一个操作执行偶数次相当于撤销。容易想到把 $3$ 操作的修改单独开一个数组存起来，另外开一个 flg 表示这个修改究竟做没做。于是我们可以 $\mathbf O(1)$ 修改。

然后还有一些具体细节，看代码。

#include<cstdio>
const int N=1e5+10,M=5e5+10;
int n,m,a[N],b[N],c[N],op[M],x[M],y[M],flg,stk[M],top;
// b 表示常规修改；c 表示 3 操作修改；flg 为 0 表示修改失败，-1 表示修改成功
inline int get(int x)//求当前 a[x]
{
	int u,v;
	for(u=1,v=a[x];u*u<x;++u)
	if(x%u==0)v^=b[u]^b[x/u]^(flg&(c[u]^c[x/u]));
	if(u*u==x)v^=b[u]^(flg&c[u]);
	return v;
}
int main()
{
	int i,u,v;scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&op[i]);
		switch(op[i])
		{
			case 1:
				scanf("%d%d",&x[i],&y[i]);
				b[x[i]]^=y[i];
				break;
			case 2:
				scanf("%d",&x[i]);
				printf("%d\n",get(x[i]));
				break;
			case 3:
				scanf("%d%d%d%d",&x[i],&y[i],&u,&v);
				while(top)b[stk[top]]^=flg&c[stk[top]],c[stk[top--]]=0;flg=0;//将之前的修改做了，清空 c 数组
				for(;u<=v;u++)if(op[u]==1)c[stk[++top]=x[u]]^=y[u];//开栈记录修改位置
				if(get(x[i])<=y[i])flg=-1;
				break;
			case 4:
				scanf("%d",&u);op[i]=op[u];x[i]=x[u];y[i]=y[u];//直接得到对应位置
				switch(op[i])
				{
					case 1:
						b[x[i]]^=y[i];
						break;
					case 2:
						printf("%d\n",get(x[i]));
						break;
					case 3:
						if(get(x[i])<=y[i])flg^=-1;//O(1) 修改
				}
		}
	}
	return 0;
}