电话！
mk14_61
·
·
题解
吃大分。
联考 T4 防 AK，我宣称此题思维难度只有黄，实现难度为紫。
思路
提供一种奇奇怪怪的理解。
以下是 $n=3,x=0\sim7,a_i = i$ 时的 $b$：
```
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
```
我们用我们敏锐的观察力注意到，当 $x$ 的第 $i$ 位为 $1$ 时，每相邻两个长为 $2^{i-1}$ 的块会交换，证明是容易的。
又因为存在子任务 $B = n$，不难想到对于序列开一颗线段树，修改就是对于某些深度的所有点交换他们的左右儿子！于是跑线段树二分就能做到 $B = n$。
对于 $B = 5/6/7$，发现建树实际只使用了 $2^n-1$ 的预处理次数，有大量的预处理次数被浪费了。
因为可能在答案序列中的节点只可能是线段树二分经过的节点的兄弟节点（但不一定包含）考虑按深度分层，处理出 $pos_{i,to,p}$ 表示第 $i$ 层内到达叶子节点编号 $to$，兄弟节点取值情况 $p$ 对应的 $a$ 的下标。
接下来就是分层的方案了，考场上想的是对于深度 $[l,r]$ 分为一层的次数是 $2^{r-l+1} \times 2^r$ 的，但实际会有重复和许多可以优化的地方（受限于作者实力就不展开了），然后写个搜子就能出方案了，搜出来的代价应该刚好是题目约束。
## 代码
> 让子集枚举都看不明白的人写这种题，真的假的？
```cpp
#include <bits/stdc++.h>
void assign(int x, int y, int z);
#define ll long long
using namespace std;
const int N = 1.1e6 + 7;
int n, m, b, t;
ll mx = 1e18;
vector<int> siz, ans;
int lowbit(int x) {return x & -x;}
ll val(int len) {//深度为len的完全二叉树的贡献
int n = (1 << len);
ll res = (1 << len) - len - 1;//节点数与叶子节点0的贡献
for (int i = 1; i < n; i ++) {
int lca = i ^ (i - 1);//得到lca(其位数表示叶子跳到lca所需次数)
int w = 0;
while (lca) {lca /= 2, w ++;}
int dep = len - w;
res += (1 << w) - w - 1;//在lca以上没有0
res += ((1 << w) - 1) * ((1 << dep) - 1);//lca以上有0
//本质就是忽略了只有lca以上有0的情况
}
return res;
}
ll get(vector<int> x) {//得到分块方案x的操作次数
ll l = 0, ans = 0;
for (int i : x) {
ans += (1 << l) * val(i);
l += i;
}
return ans;
}
void dfs(int n, int u, int lst, vector<int> x) {
if (u == b && n == 0) {
ll w = get(x);
if (w < mx)
mx = w, siz = x;
}
if (u >= b || n <= 0)
return;
int lim = min(lst, n);
for (int i = 1; i <= lim; i ++) {
x.push_back(i);
dfs(n - i, u + 1, i, x);
x.pop_back();
}
}
struct Segtree {
int idx, id[21][N];
vector<vector<int>> pos[9];//第i层叶子节点为j,取值情况为k
void build() {
for (int i = 0; i < (1 << n); i ++)
id[n][i] = i;
for (int i = n - 1; i >= 0; i --) {
for (int j = 0; j < (1 << i); j ++) {
id[i][j] = ++ idx;
assign(id[i + 1][j * 2], id[i + 1][j * 2 + 1], idx);
}
}
}
void dfs(int c, int u, int dep, int to, vector<int> num) {
if (dep == to) {
int len = num.size();
for (int p = 0; p < (1 << len); p ++) {//兄弟节点(num)的取值情况
pos[c][u].push_back(m - 1);
if (p == 0)
continue;
else if (lowbit(p) == p) {//有且仅有一个1
for (int i = 0; i < len; i ++) {
if (p & (1 << i))
pos[c][u][p] = num[len - i - 1];
}
}
else if (u % (1 << len) != 0 && lowbit(p) > (u ^ (u - 1))) {
//如果不是第一个被遍历到的节点且取值p已经被处理
pos[c][u][p] = pos[c][u - 1][p];//继承
}
else {//开新节点
pos[c][u][p] = ++ idx;
for (int i = 0; i < len; i ++) {
if (p & (1 << i)) {
assign(num[len - i - 1], pos[c][u][p - lowbit(p)], idx);
break;
}
}
}
}
return;
}
num.push_back(id[dep + 1][u * 2 + 1]);
dfs(c, u * 2, dep + 1, to, num);
num.pop_back();
num.push_back(id[dep + 1][u * 2]);
dfs(c, u * 2 + 1, dep + 1, to, num);
num.pop_back();
}
void init() {
int l = 0, r = 0, i = -1;
for (int len : siz) {
i ++, r += len;
for (int j = 0; j < (1 << r); j ++)
pos[i].push_back({});
for (int rt = 0; rt < (1 << l); rt ++)
dfs(i, rt, l, r, {});
l += len;
}
}
}tr;
void init(int n, int m, int a, int b) {
::n = n, ::m = m, tr.idx = (1 << n);
::b = min({b, n, 7});
dfs(n, 0, n, {});
tr.build();
tr.init();
}
vector<int> query(int x, int y) {
t ^= x, y ++;
ans.clear();
if (y == (1 << n))
return {tr.id[0][0]};
int low = n, lto = 0;
for (int i = 0; i < siz.size(); i ++) {
low -= siz[i];
int len = siz[i];
int to = (t ^ y) >> low & ((1 << len) - 1);//取出x^y的low~low+len作为块内的路径
to += lto * (1 << len);
int p = y >> low & ((1 << len) - 1);//取出y的low~low+len作为兄弟节点的取值情况
int u = tr.pos[i][to][p];
ans.push_back((u < (1 << n) ? u ^ t : u));
lto = to;
}
return ans;
}
/*
20 20000000 10 2522795 5 1000000000
B = 5 ： 9 5 3 2 1
B = 6 ： 8 5 3 2 1 1
B = 7 ： 8 4 3 2 1 1 1
*/
```