洛谷P7442 「EZEC-7」维护序列 题解
题目链接：P7442 「EZEC-7」维护序列
题意：
你需要维护一个序列。
这个序列开始时有 \(2^n\) 个数，下标从 \(0\) 开始。第 \(i\) 个数初始值为 \(i\)，需要支持以下三种操作：
- 定义 \(a\) 为所有下标为偶数的数组成的子序列，\(b\) 为所有下标为奇数的数组成的子序列，将 \(a,b\) 连接，构成新的序列。
- 定义 \(a\) 为所有下标为奇数的数组成的子序列，\(b\) 为所有下标为偶数的数组成的子序列，将 \(a,b\) 连接，构成新的序列。
- 查询下标为 \(x\) 的数。
总共将进行 \(m\) 次操作。
输入格式：
第一行输入两个正整数 \(n,m\)。
接下来输入 \(m\) 行，每行输入两个非负整数 \(\mathtt{op},x\)，代表一次操作。
如果 \(\mathtt{op}=1\)，若 \(x=0\)，代表第一种操作，若 \(x=1\)，代表第二种操作。
如果 \(\mathtt{op}=2\)，代表第三种操作，参数 \(x\) 即为输入的 \(x\)。
输出格式：
对于每个 \(\mathtt{op}=2\) 输出一行，即对应的数。
数据范围：
对于 \(100\%\) 的数据，\(1\leq n\leq 32\)，\(1\leq m\leq 10^6\)。
若 \(\mathtt{op}=1\)，\(x\in\{0,1\}\)，若 \(\mathtt{op}=2\)，\(0\leq x<2^n\)。
结论题。发现 \(n=3\) 时，进行 \(3\) 次操作2就会变回来。
因此这个一定与二进制有关系。并且根据置换的性质，对数操作等价于对下标做逆操作
于是考虑每个下标 \(x\) 会怎么移动。
- 操作1：把 \(x\) 的二进制位循环左移一位（最高位会移到最低位）
- 操作2：同操作 \(2\) ，不过循环左移后最后一位取反（异或上 \(1\) ）
我们只要记录移动的次数和哪些位需要异或即可
时间复杂度 \(\mathcal{O}(m)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())
int n,Q,t,cnt,x,y;
int solve(int x,int y)
{
t = x >> (n-cnt);
t |= (x & ((1ll<<(n-cnt)) - 1))<<cnt;
return t ^ y;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> Q;
for(int op; Q--; )
{
cin >> op >> x;
if(op == 1)
{
if(x == 1) y ^= (1ll << cnt);
++cnt;
if(cnt >= n) cnt -= n;
}else
{
if(cnt) cout << solve(x,y) << '\n';
else cout << (x ^ y) << '\n';
}
}
return 0;
}参考文献：
