非常有意思的一道题(虽然确实容易想不出来)。
题意
维护一个 $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;
}