分析
刚开始此题被放在了第一道，第一眼我没有算对复杂度，写了一个极易理解的暴力算法，而且还因为看错下标做得更加麻烦，思路是这样的。
for(int i=tot;i>=1;i--){
if(cz[i]==0){
if(x<=mid){
x=2*x-1;
}
else {
x=(x-mid)*2;
}
}
if(cz[i]==1){
if(x<=mid){
x=x*2;
}
else {
x=(x-mid)*2-1;
}
}
}
return x-1;
很明显，\(m^2\) 的复杂度，经过找规律我发现对于第一种操作，如果连续 \(n\) 次就会抵消，以上是暴力加捆绑点5的思路。
从序列大小为 \(2^n\)，我们可以试试二进制位运算，随机设几组 \(n\) 然后进行两种操作的修改，我们发现，对于操作一，就是对于偶数位置的数，将它的坐标改为了原来的一半，奇数位置则是移至一半加上 \(\frac{n}{2}\)，然后就是很明显，就是不断地将它的下标二进制集体向右转一位，最后一位转到前面来，然后将它回溯，转回去，其实就是在2进制上将暴力的一个个回溯改为了位运算的单次运算方法，这也可以解释为什么操作一进行 \(n\) 次之后就会抵消，而操作二经过演算，发现就是先移动再异或上一，所以这道题就这么搞定了。
代码
#include<bits/stdc++.h>
using namespace std;
#define int unsigned int
int cnt,op,x,n,m,y;
inline void read(int &res){
res=0;
int f=1;
char c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){res=(res<<1)+(res<<3)+c-48;c=getchar();}
res*=f;
}
inline void write(int x){
if(x==0){
putchar(‘0‘);
return;
}
char f[205];
int tmp=x>0?x:-x;
if(x<0)putchar(‘-‘);
int cnt=0;
while(tmp>0){
f[cnt++]=tmp%10+‘0‘;
tmp/=10;
}
while(cnt>0)putchar(f[--cnt]);
}
signed main()
{
read(n);read(m);
while(m--){
read(op);read(x);
if(op==1){
if(x==1){
y^=1<<cnt;
}
cnt++;
if(cnt>=n)cnt=0;
continue;
}
write(((x>>(n-cnt))|((x&((1<<(n-cnt))-1))<<cnt))^y);
putchar(10);
}
return 0;
}