cf Educational Codeforces Round 133 E. Swap and Maximum Block

原题：
E. Swap and Maximum Block
time limit per test4 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
You are given an array of length $2^n$. The elements of the array are numbered from 1 to $2^n$.

You have to process q queries to this array. In the i-th query, you will be given an integer k (0≤k≤n−1). To process the query, you should do the following:

for every i∈[1,$2^n-2^k$] in ascending order, do the following: if the i-th element was already swapped with some other element during this query, skip it; otherwise, swap ai and $a_{i+2^k}$;
after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment).
For example, if the array a is [−3,5,−3,2,8,−20,6,−1], and k=1, the query is processed as follows:

the 1-st element wasn’t swapped yet, so we swap it with the 3-rd element;
the 2-nd element wasn’t swapped yet, so we swap it with the 4-th element;
the 3-rd element was swapped already;
the 4-th element was swapped already;
the 5-th element wasn’t swapped yet, so we swap it with the 7-th element;
the 6-th element wasn’t swapped yet, so we swap it with the 8-th element.
So, the array becomes [−3,2,−3,5,6,−1,8,−20]. The subsegment with the maximum sum is [5,6,−1,8], and the answer to the query is 18.

Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.

Input
The first line contains one integer n (1≤n≤18).

The second line contains 2n integers a1,a2,…,a2n ($-10^9\le a_i\le 10^9$).

The third line contains one integer q (1≤q≤$2\cdot 10^5$).

Then q lines follow, the i-th of them contains one integer k (0≤k≤n−1) describing the i-th query.

Output
For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.

Example
input
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
output
18
8
13
Note
Transformation of the array in the example: [−3,5,−3,2,8,−20,6,−1]→[−3,2,−3,5,6,−1,8,−20]→[2,−3,5,−3,−1,6,−20,8]→[5,−3,2,−3,−20,8,−1,6].

中文：
给你一个$2^n$长度的序列，然后再给你一个整数q，表示有q个查询，每个查询给你一个整数k，整数k会对上面长度为$2^n$的序列进行如下操作：
每次交换序列中$a_i$以及$a_{i+2^k}$，如果某个元素交换过，则跳过。
比如k=1，会交换$(a_1,a_3)$, $(a_2,a_4)$, $(a_5,a_7)$, $(a_6,a_8)$ …
并输出交换后的区间中的最大字段和。
第i次查询会继承第i-1次查询交换后的序列状态。

代码：

#include 
using namespace std;
 
const int maxn = 2e5 + 2;
typedef long long ll;
 
 
struct Node {
  ll pre, suf, mx, sum;
  Node(ll x = 0) {
    pre = suf = mx = max(0LL, x);
    sum = x;
  }
  Node operator+(const Node& rhs) {
    Node res;
    res.pre = max(pre, sum + rhs.pre);
    res.suf = max(rhs.suf, suf + rhs.sum);
    res.mx = max({ mx, rhs.mx, suf + rhs.pre });
    res.sum = sum + rhs.sum;
    return res;
  }
};
 
int n, m;
vector<vector<Node>> f;
vector<ll> ans;
vector<int> a;
 
void dfs(int level, int status) {
  int child_num = 1 << (n - level);
  if (level != 0) {
    for (int i = 0; i < child_num; i++) {
      int lef = i << 1;
      int rig = lef | 1;
      f[level][i] = f[level - 1][lef] + f[level - 1][rig];
    }
  }
  if (level == n) {
    ans[status] = f[level][0].mx;
    return;
  }
  dfs(level + 1, status);
  
  child_num >>= 1;
  for (int i = 0; i < child_num; i++) {
    int lef = i << 1;
    int rig = lef | 1;
    swap(f[level][lef], f[level][rig]);
  }
  dfs(level + 1, status | 1 << level);
}
 
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  m = 1 << n;
  a.resize(m + 1);
  f.resize(n + 1);
  ans.resize(m + 1);
  for (int i = 0; i < m; i++) {
    cin >> a[i];
  }
 
  for (int i = 0; i <= n; i++) {
    f[i].resize(1 << (n - i));
  }
 
  for (int i = 0;i < m; i++) {
    f[0][i] = a[i];
  }
  dfs(0, 0);
 
  int q, k;
  cin >> q;
  int status = 0;
  while (q--) {
    cin >> k;
    status ^= 1 << k;
    cout << ans[status] << endl; 
  }
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

解答:
参考了别人的代码，发现内存可以开这么大…

如果要做到每次查询都能得到最大子段和，那么需要用一个数据结构来维护这个数据。
这个数据结构能计算最大字段和，很容易想到用线段树。但是如何在线段树上维度交换的这个操作？

题目中给出交换的操作是交换$a_i$以及$a_{i+2^k}$
需要能够发现如下的规律:
比如n = 8，有序列[1, 2, 3, 4, 5, 6, 7, 8]
当k等于0时，交换后的序列为:
[2, 1, 4, 3, 6, 5, 8,7]，即相邻的两个数字交换。
当k等于1时，交换后的序列为:
[3, 4, 1, 2, 7, 8, 5, 6]
当k等于2时，交换后的序列为:
[5, 6, 7, 8, 1, 2, 3, 4]
可以发现，不同的k值交换后得到的序列呈现处一种“层次”关系。
比如k等于2的时候，是将序列分成两半，然后交换。
k等于1时，是将序列从头开始两个一组，分成4段，然后逐个交换。

此外，查询的某个k值如果出现了偶数次时，相当于没有任何交换操作。

以上两个规律还是比较明显的，还有一个规律需要考虑。
如果是2的次幂数的规律，那很容易想到位运算的表示方式。

按照tutorial中给出的解释:
如果是二进制的方式表示这$2^n$次幂个数的位置（下标从0开始），如果交换$a_i$和$a_{i+2^k}$。从二进制的表示来看，即将所有位置下标的二进制的第k位从0变成1，1变成0.
例如有8个数，这8个数的位置用二进制表示位:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111
1

如果k=2，按照题目要求，会将序列前半段和后半段的位置对换。对换后的二进制表示为

0100, 0101, 0110, 0111, 0000, 0001, 0010, 0011
1

那么，可以用二进制的方式来索引每个节点的位置信息。

此外，可以使用状态压缩的方法来记录所有交换可能下的最大子段和。那么，所有的交换可能共有$2^k$种，如果查询的时，k值为1，只需要对上一次查询状态的值在第k位进行抑或即可。

计算时使用线段树，将序列套在线段树上来维护最大字段和。线段树计算最大字段和的方式可以用分治的思想实现。
设置状态f[level][state]，其中level表示层级，level=0表示将序列每个数作为单独的节点考虑最大字段和，level=1表示将相邻两对元素作为节点考虑最大字段和，如此类推。status表示所有k的二进制状态。