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

· · 题解

最开始时由于某些原因这题是第一题。

我做了半个小时才做出来，心想第一题都这么难，第二题肯定做不出来了。

结果只花了 5 分钟就做出了 “第二题”。

进入正题：

先考虑 1 操作。

以长度为 2^3 = 8 的序列为例。

初始序列：

十进制 二进制
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

操作后：

十进制 二进制
0 000
2 010
4 100
6 110
1 001
3 011
5 101
7 111

再次操作：

十进制 二进制
0 000
4 100
1 001
5 101
2 010
6 110
3 011
7 111

观察它们的二进制有什么规律？

我们发现一次操作相当于将二进制首位移到末位，其他位向左移一格。

也就是说，将二进制的各位按顺时针连成一个环，并将该环逆时针旋转一格。

开一个变量记一下旋转的次数即可。

如果旋转了整整一圈，一定记得要归零！！！

再来看一下 2 操作： 1 操作 二进制 2 操作 二进制
0 000 1 001
2 010 3 011
4 100 5 101
6 110 7 111
1 001 0 000
3 011 2 010
5 101 4 100
7 111 6 110

不就是 \operatorname{xor} 一下 1 吗？

另开一个变量记一下要 \bold{xor} 的数即可。

用位运算，\Theta(m)，比大伙们的 \Theta(nm) 快多了。

还有：

unsigned int

因为：

x \in [0, 2^{32})

而 int 的表示范围为

[-2^{31}, 2^{31})

你用 long long 没人拦着你

#include <bits/stdc++.h>
using namespace std;
int n, m, o;
unsigned x, y;

inline unsigned read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

inline void write(unsigned x)
{
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int cnt;
int main() {
    n = read();
    m = read();
    while (m--) {
        o = read();
        x = read();
        if (o == 1) {
            if (x) {
                y = y ^ (1<<cnt);
            }
            cnt++;
            if (cnt == n) cnt = 0;
        } else {
            if (cnt) write(((x>>(n-cnt))|((x&((1<<(n-cnt))-1))<<cnt))^y);
            else write(x^y);
            putchar(10);
        }
    }
    return 0;
}