感觉以前遇到过类似的操作，但是还是不会（
考虑到两次相同的操作会相互抵消，并且答案与操作顺序无关，所以答案至多 \(2^n\) 种，考虑预处理出来。
首先你得会分治求最大子段和，维护 \(lmx,rmx,mx,sum\)，分别表示一段区间的前缀最大子段和，后缀最大子段和，最大子段和，区间和。
于是可以 merge 出当前区间的答案：
node operator + (const node &rhs) {
node res;
res.lmx = max(lmx, sum + rhs.lmx);
res.rmx = max(rhs.rmx, rhs.sum + rmx);
res.mx = max(max(mx, rhs.mx), rmx + rhs.lmx);
res.sum = sum + rhs.sum;
return res;
}
然后发现该序列可以建出一棵满二叉树，对某一位操作相当于交换这棵树对应层的左右节点，并且每层之间互不影响。
那么设 \(f_{i,j}\) 表示在编号为 \(i\) 的节点，操作集合为 \(j\) 的答案。
设 \(i\) 的左右儿子分别为 \(lc,rc\)。
如果下面一层不换，那么 \(f_{i,j}=f_{lc,j}\oplus f_{rc,j}\)。
否则 \(f_{i,j}=f_{rc,j}\oplus f_{lc,j}\)。
其中 \(\oplus\) 就是上面的 merge。
但是这样空间开销太大，于是每层递归都返回一个 vector 就好了。
时间复杂度 \(\mathcal O(n\times 2^n+Q)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 18) + 5;
int n, Q;
ll a[N];
struct node {
ll lmx, rmx, mx, sum;
node (){}
node (ll _lmx, ll _rmx, ll _mx, ll _sum) {
lmx = _lmx, rmx = _rmx, mx = _mx, sum = _sum;
}
node operator + (const node &rhs) {
node res;
res.lmx = max(lmx, sum + rhs.lmx);
res.rmx = max(rhs.rmx, rhs.sum + rmx);
res.mx = max(max(mx, rhs.mx), rmx + rhs.lmx);
res.sum = sum + rhs.sum;
return res;
}
};
vector <node> solve(int l, int r) {
if (l == r) return vector <node> {node(a[l], a[l], a[l], a[l])};
int mid = l + r >> 1;
auto resL = solve(l, mid), resR = solve(mid + 1, r);
int k = resL.size();
vector <node> res(k * 2);
for (int i = 0; i < k; ++i) {
res[i] = resL[i] + resR[i];
res[i + k] = resR[i] + resL[i];
}
return res;
}
int main() {
scanf("%d", &n), n = 1 << n;
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
auto ans = solve(1, n);
int cur = 0; scanf("%d", &Q);
while (Q--) {
int x; scanf("%d", &x);
cur ^= 1 << x, printf("%lld\n", max(0ll, ans[cur].mx));
}
return 0;
}