同步发布于 here。
用树状数组优化了一下的解法。虽然我也不知道优没优化。
做法
首先这个格雷码明显可以预处理。
然后对于一次操作一，因为我们 \(\sum m \le 5000\)，所以其实我们直接暴力的枚举就可以了，但是我复杂度算错了，以为成了 \(O(q^22^n)\)，那肯定过不了啊，然后我就写了一个 BIT，这样优化到了我以为的 \(O(q^2 n)\)，实则应该是 \(O(q n)\)。
具体实现就是我们用 BIT 维护 \([1,2^{k_i} - 1]\) 区间的修改次数，因为格雷码 \([2^n,2^{n+1} - 1]\) 是有环的，我们就可以在环中去做，这样我们求出对应的修改次数后模环长后暴力修改的时间复杂度也是对的。
有人会说题目中不是说要求 \(a_j < 2^{k_i}\) 才修改吗，但是我们的循环节最大的位置是到 \(2^n-1\) 的，所以如果一个位置被修改则这个位置一定在下一次有 \(j < 2^{k_i}\) 还能被修改。
对于操作二我们就如上面所说求一下第 \(i\) 个点的修改次数，对环长取模后暴力修改即可，时间复杂度 \(O(q 2^ n)\)。
时间复杂度应该是 \(O(2^n + q n + q 2^n)\)。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e6 + 66;
int n, m;
vector<int> v[N];
int a[N];
struct BIT{int tr[N];int lowbit(int x){return x & -x;}void add(int x, int v){for(;x <= n;x += lowbit(x)) tr[x] += v;}ll query(int x){int res = 0;for(;x;x -= lowbit(x)) res += tr[x];return res;}
}b;//树状数组
int ck(string s)//二进制转十进制
{int res = 0, p = 1;for(int i = s.size() - 1;i >= 0;i --, p *= 2) res += (s[i] - '0') * p;return res;
}
string ckk(int x)//十进制转二进制
{string s;if(x == 0) s = "0";while(x) s += (char)(x % 2 + '0'), x /= 2;reverse(s.begin(), s.end());return s;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);v[1] = {0, 1};for(int i = 2;i <= 10;i ++){int p = 1 << i - 1;v[i] = v[i - 1];//前面的和 n-1 一样for(int j = v[i - 1].size() - 1;j >= 0;j --) v[i].push_back(v[i - 1][j] + p);//后面的按题意模拟}//预处理格雷码cin >> n >> m;n = 1 << n;for(int i = 0;i < n;i ++) a[i] = i;while(m --){int op, l, x;cin >> op;if(op == 1){cin >> l;for(int i = 1;i <= l;i ++){cin >> x;x = 1 << x;//实际下标b.add(1, 1);b.add(x, -1);//差分}}else {string s;cin >> s;l = ck(s);x = b.query(l);//修改次数x %= 1 << ((int)log2(l) + 1);//实际要走的步数int ans = a[l];//原位置while(x --) ans = v[10][ans];//直接在最大的格雷码上走就可以了，因为前面都是一样的cout << ckk(ans) << '\n';}}return 0;
}