题解 P7346 【DSOI 2021】归零

· · 题解

首先，由于修改复杂度较大，所以我们考虑修改打 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;
}