题意：
给定一个序列 \(A_{0, ..., 2^k - 1}\)。
要执行 \(q\) 次如下操作：
- 给定 \(x_i, y_i\)。对于 \(0,...,2^k-1\) 中的所有数 \(j\)，如果 \(j\) 的第 \(x_i\) 位为 \(y_i\)，那么令 \(j'\) 为 \(j\) 翻转第 \(x_i\) 位（\(0\) 变 \(1\)，\(1\) 变 \(0\)）之后的数，将 \(A_{j'}\) 加上 \(A_j\)。
求操作后的序列。
\(k \le 18, q \le 2 \times 10^5,y_i \in \{0,1\}, x_i \in [0,k-1]\)
分析：
首先这个题目暴力做是 \(O(nq)\) 的，并且没有什么突破口，只可能是 \(O(kq)\)。（\(O(n \sqrt q)\) 不是不可能，但是我显然不可能会的）
那么显然考虑能不能把询问拿来排序并按位处理。
要想知道能否排序，关键在于是否能够邻项交换。通过模拟我们发现如果 \(x_i \neq x_{i+1}\)，那么是可以交换的。（这个东西我还没有感性理解，只知道模拟之后是这样的）
于是我们只需要按照 \(x_i\) 为关键字，稳定排序所有询问。注意 sort 并不是稳定排序（这个是个坑，会发现小数据上似乎是稳定的，但是其实大数据实现不同）。stable_sort 是。还可以手动稳定，也就是用 ind 作为第二关键字。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = a; i <= b; i++)
const int mod = 998244353;
int n, q;
int a[300010];
struct query{
int x, y, ind;
}b[300010];
bool cmp(query ca, query cb) {
if(ca.x != cb.x) return ca.x < cb.x;
else return ca.ind < cb.ind;
}
vector<query> sol;
void solve() {
int bit = sol[0].x;
int xa = 1, xb = 0, ya = 1, yb = 0;
for(query now : sol) {
if(now.y == 0) {
ya += xb, yb += xa;
ya %= mod, yb %= mod;
}
else {
xa += yb, xb += ya;
xa %= mod, xb %= mod;
}
}
f(i, 0, (1 << n) - 1) {
if(!((i >> bit) & 1)) {
int nxt = (i | (1 << bit));
int tx = a[i], ty = a[nxt];
a[i] = (xa * tx % mod + xb * ty % mod) % mod;
a[nxt] = (ya * ty % mod + yb * tx % mod) % mod;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> q;
f(i, 0, (1 << n) - 1) cin >> a[i];
f(i, 1, q) cin >> b[i].x >> b[i].y;
f(i, 1, q) b[i].ind = i;
sort(b + 1, b + q + 1, cmp);
f(i, 1, q + 1) {
if(i != 1 && (i == q + 1 || b[i].x != b[i - 1].x)) {
solve(); sol.clear();
}
if(i == q + 1) break;
sol.push_back(b[i]);
}
f(i, 0, (1 << n) - 1) cout << a[i] << " ";
}