一年之后再看好歹是会双log做法的84分的，虽然可能被卡常
首先显然有 \(x\oplus y\le x+y\)。
对于一个最优的方案 \(S,x\) 你显然如果不影响 $\oplus $ 部分的最值的话移走的最优的。
所以我们只会将会影响 $\oplus $ 部分最值的留在 \(S\)。
考虑二分答案 \(mid\)，判断有没有 \(\ge mid\) 的方案。
则因为 \(x\oplus y\le x+y\)，所以事实上有：
\[mid\le \min(\min_{i\in S}(a_i+x),\min_{i\notin S}(a_i\oplus x))\implies mid\le \min(\min (a_i+x),\min_{i\notin S}(a_i\oplus x)) \]而那么在满足 \(x\ge mid-a_{\min}\) 的条件之下，如果不满足 \(a_i\oplus x\ge mid\)，则必然需要加入 \(S\)，且尽可能少加入。
则可以得到存在合法方案的充要条件是：
\[\exists x\in [mid-a_{\min},2^k-1],\sum_{a_i\oplus x<mid}b_i\le m \]考虑将 \(a_i\oplus x\) 与 \(mid\) 作比较，感觉 \(x\) 很容易贪心地填 \(1\)。
转化对象，以 \(a_i\) 为主元。
感觉如果有 \(a_i\oplus x<mid\)，那么显然可以数位DP划分出 $\log $ 个区间，那么就可以变成区间加，然后全局最小值查询了。
这样就得到了 $3\log $ 做法
优化？
其实还是对应了 \(trie\) 上的点，所以可以变成 \(trie\) 上的单点加全局 \(\min\) 维护。
感觉还是容易的，得到了 $2\log $ 做法。
然后我们需要一个后缀 min，可以实现
考虑Trie的实现细节
其实是看 \(mid\) 的每一位和 \(x\) 当前的每一位，然后统一算所有走到这里的 \(a\) 的贡献，其实这个 \(a\) 应该是在子树内部。
所以我们需要维护一个子树内 \(b\) 的和。
-
\(bit(mid)=1\)，则
取 \(x=1\) 相当于继续递归左子树，而左子树可以直接加上右子树的 \(b\) 了
取 \(x=0\) 相当于继续递归右子树，而右子树可以直接加上左子树的 \(b\) 了。
-
\(bit(mid)=0\)，则
取 \(x=1\) 相当于继续递归右子树，左子树已经解决
取 \(x=0\) 相当于继续递归左子树，右子树已经解决
所以可以子树内维护当前位置 \(mid\) 是 \(1\)，更低位置全 \(0\) 在子树内是否有解，也就是要求 \(x\ge mid-a_1\)，所以我们维护有解的最大 \(x\)？
我们不妨设一个 \(sol(p,mid,dep,now,mna,sumb)\)
也就是当前划分到的集合 \(S\) 里的 \(mna\)，当前节点是 \(p\)，深度 \(dep\)，当前得到的答案是 \(mid\)，当前填的 \(x\) 是 \(now\)，当前已经得到了 \(sumb\) 的加法标。
枚举当前 \(mid\) 和 \(now\) 怎么取的 \(4\) 类情况讨论即可
ll sol(int p,int dep,ll mid,ll now,ll mna,int sumb){
if(sumb>m)return 0;
if(dep<0)return mid;
ll res=0;
//mid=1,now=1，递归左子树，算上右子树b
//mid+=pw[d],now+=pw[d]
int lc=ch[p][0],rc=ch[p][1];
ll lmna=min(ma[rc],mna),rmna=min(ma[lc],mna);
if(pw[dep]+now+pw[dep]-1+lmna>=mid+pw[dep]){
res=max(res,sol(lc,dep-1,mid+pw[dep],now+pw[dep],lmna,sumb+sb[rc]));
}
//mid=1,now=0，递归右子树，算上左子树b
if(now+pw[dep]-1+rmna>=mid+pw[dep]){
res=max(res,sol(rc,dep-1,mid+pw[dep],now,rmna,sumb+sb[lc]));
}
if(res>0)return res;
//mid=0,now=1，递归右子树，左子树无贡献，mna无需更新
if(pw[dep]-1+pw[dep]+now+mna>=mid){
res=max(res,sol(rc,dep-1,mid,now+pw[dep],mna,sumb));
}
if(pw[dep]-1+now+mna>=mid){
res=max(res,sol(lc,dep-1,mid,now,mna,sumb));
}
return res;
}
然后优先 \(mid\) 是 \(1\) 的解，大力递归就好了。我们每一层根据 \(mna+now\ge mid\) 来减枝，可以保证每次往下搜的时候只要能够递归就可以得到解，所以每个点只会递归一次，复杂度 \(O(Tnk)\)
这贪心是真NB
这个题涉及到了很多技巧：
- 贪心将不会影响答案的东西移走，使最优方案更容易满足边界条件
- 整体与单体的视角转化，\(\sum_{a_i\oplus x<mid}b_i\) 从枚举 \(x\) 单体——整体计算变成对于每个 \(a_i\) 的单体整体统计贡献，有时候正难则反。
- 限制条件的解决形式，如 \(x\ge [mid-a_{\min},2^k-1]\) 不用再计算单 \(a_i\) 贡献时考虑边界，而是在贡献完之后整体照边界
- 位运算题目，二分答案往往可以被按位贪心讨论简化掉。