P7442 「EZEC-7」维护序列 题解

发布于 2021-03-25  225 次阅读


非常有意思的一道题(虽然确实容易想不出来)。

题意

题目链接

维护一个 $0 \sim 2^n-1$ 的序列,支持两个操作:将下标为偶数的数按序提前,将下标为奇数的数按序后置;将下标为偶数的数按序后置,将下标为奇数的数按序提前。

解析

我们考虑两种操作的实质。

第一种操作(偶前奇后):对于下标为 $x$ 的数,若 $x$ 为偶数,则它的新下标为 $\frac{x}2$;若 $x$ 为奇数,则它的新下标为 $\frac{x}{2}+\frac{n}{2}$。

第二种操作(奇前偶后):对于下标为 $x$ 的数,若 $x$ 为偶数,则它的新下标为 $\frac{x}{2}+\frac{n}{2}$;若 $x$ 为奇数,则它的新下标为 $\frac{x}{2}$。

见到这么多的除以二,我们考虑到二进制。我们假定一个操作前某数的下标为 $x=(a_na_{n-1}a_{n-2} \dots a_2a_1 )$,同时我们又发现偶数的末位为 $0$,奇数的末位为 $1$,那么我们进行一次一操作,就是将下标变为 $(a_1a_na_{n-1} \dots a_3a_2 )$,也就是将最后一位移到第一位,再将其他位都向后推一位。同样能够发现,我们进行一次二操作,就是将下标变为 $((a_1\operatorname{xor}1)a_na_{n-1} \dots a_3a_2 )$,也就是将末位异或 $1$ 之后再进行之前的操作。因此假设我们进行 $t$ 次操作后($t < n$),就是把最后的 $t$ 位以相同的顺序移到了前面(即,若原先三位在最后是 $(a_3a_2a_1)$ ,则它被移到了前面之后这三位依然是 $(a_3a_2a_1)$,内部顺序不变),把其他位移到了最后(当然其中可能有一些需要异或)。

现在,我们得到的是一个操作后的数的下标,输出对应的数其实就是输出原始的下标。因此,我们可以用 $cnt$ 记录一下进行了几次一操作(容易发现,当 $n=cnt$ 时,所有位都移了一轮,此时可以将 $cnt$ 归零),然后将这个数的末 $n-cnt$ 位向前移 $cnt$ 位,将最前的 $cnt$ 位向后移动 $n-cnt$ 位,这样,我们就得到了原先的数,但是注意,我们此时尚未处理异或操作。

容易发现,每次异或实际是对第 $cnt+1$ 位进行异或,那么我们可以用一个变量 $v$ 记录原始每一位上是否需要异或,详见代码注释。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60;
int n,m,t[N],v,x,opt,cnt;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) t[i]=(t[i-1]<<1)+1;//可以提前处理一下全 1 数
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&opt,&x);
        if(opt==1){
            v^=x<<cnt;//将第 cnt+1 位打上标记,若 x=0 显然这个操作是无意义的
            cnt++;
            if(cnt==n) cnt=0;//如果 cnt=n 了,一轮结束,cnt 归零
        }
        else{
            printf("%lld\n",(((x&t[n-cnt])<<cnt)|(x>>(n-cnt)))^v);
            //(x&t[n-cnt])<<cnt 是将最后 n-cnt 位向前移动
            //x>>(n-cnt) 是将前 cnt 位向后移动,再用 | 合并
            //由于我们前面的标记打在原始序列上,所以要先将该数列还原后再 ^v
        }
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣