\(O(nk^2)\)
我们考虑如果确定了 \(ans\)，如何判断是否合法？
考虑从高到低逐位确定 \(x\)。
设 \(ans\) 和 \(x\) 的第 \(i\) 位为 \(ans_i,x_i\)。
分类讨论一波：
如果 \(ans_i\) 为：
-
0：无论 \(x_i\) 取什么，总有一边在异或 \(x\) 后第 \(i\) 位为 1。
- \(x_i=0\)，那么右子树一定比 \(ans\) 大。所以向左子树递归。
- \(x_i=1\)，同理，向右子树递归。
-
1：无论 \(x_i\) 取什么，总有一边在异或 \(x\) 后第 \(i\) 位为 0，小于答案。所以一定有一颗子树全部使用加法。
- \(x_i=0\)，那么左子树在只使用异或时一定比 \(ans\) 小。所以左子树全部使用加法。向右子树递归。
- \(x_i=1\)，同理，向左子树递归。
注意到当 \(ans_i=1\) 时一颗子树就算全部加法也不一定安稳，仍有可能小于 \(ans\)。
所以需要给 \(x\) 限制最小值 \(mnx\)，表示应当有求出的 \(x\geq mnx\)。
因为用加法的每个数加上 \(x\) 都应当 \(\geq ans\)。所以当 \(ans_i=1\) 时可以用 （\(ans\ -\) 加法子树内 \(a\) 的最小值） 更新 \(mnx\)。
如果搜到第 \(i\) 位时 \(x+2^i-1<mnx\)，这个分支就没救了，直接返回。
如果有搜到最后的，说明 \(ans\) 可能。二分即可。
单次判断 \(O(nk)\)，二分 \(O(k)\)。总复杂度 \(O(nk^2)\)。
\(O(nk)\)
线段树上二分可以去掉一只 \(\log\)，Trie 树上二分是不是可以去掉一个 \(k\)？
考虑逐位确定 \(ans\)。
注意到一个性质，如果 \(ans\) 开始确定第 \(i\) 位，如果接下来 \(i\) 位的确定方式中有一种可行，那么低 \(i\) 位全部置 0（设为 \(ans0\)）也一定可行。
所以当前分支可能当且仅当接下来 \(i\) 位都为 0 也可能。
这是容易的。
设当前已经确定的 \(x\) 为 \(x0\)。
因为当前子树去掉低 \(i\) 位都和 \(ans0\) 相等，所以只要考虑加法子树。
设加法子树的最小值为 \(mnv\)，那么 \(x\geq ans0-mnv\)。
因为 \(x\leq x0+2^{i+1}-1\)，所以有解当且仅当 \(sumcost<m\) 并且 \(ans0-mnv< 2^{i+1}+x0\)。
所以只要维护 \(sumcost,x,ans,mnv\) 即可。
特判一下如果到了空子树，那么答案直接是 \(\min(ans + 2^{i+1} - 1, mnv + x + 2^{i+1} - 1)\)，就是 \(mnv\) 可以够到的最大值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using LL = __int128;
namespace fastio {
const int mxn = 1 << 22;
char buf[mxn], *S = NULL, *T = NULL;
inline char Getchar(){return (S == T ? T = (S = buf) + fread(buf, 1, mxn, stdin) : 0, S == T ? EOF : *S++);}
template <typename T> void read(T &x)
{
x = 0; char c = 0;
for(c = Getchar(); c != EOF && (c < '0' || c > '9'); c = Getchar());
while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = Getchar();
}
template <typename T, typename... _T> void read(T &x, _T&... y){read(x);read(y...);}
void write(LL x)
{
if(x > 9)write(x / 10);
putchar(x % 10 + '0');
}
inline void printLL(LL x) {write(x); putchar('\n');}
}
using fastio::read, fastio::printLL;
const int N = 1e5 + 5, K = 120, W = 7;
int n, m, k;
LL a[N], mn[N << W], val[N << W];
int b[N], sc[N << W];
int s[N << W][2], idx;
inline int nw(int &x) {return x ? x : x = ++idx;}
void ins(int x, int lev, LL v, int cost)
{
while(lev >= -1)
{
mn[x] = min(mn[x], v ^ ((v >> lev + 1) << lev + 1));
val[x] = min(val[x], v);
sc[x] = min((int)(1e9 + 5), sc[x] + cost);
x = nw(s[x][(v >> lev) & 1]);
if(lev < 0) val[x] = v;
lev --;
}
}
void init()
{
memset(mn, 0x3e, sizeof(mn[0]) * ((n * k) + 5));
memset(val, 0x3e, sizeof(val[0]) * ((n * k) + 5));
memset(sc, 0, sizeof(sc[0]) * ((n * k) + 5));
memset(s, 0, sizeof(s[0][0]) * ((n * k * 2) + 10));
idx = 1;
}
LL ans;
bool dfs(int x, int lev, int nc, LL now, LL mnv, LL nowans)
{
const LL v1 = (LL)1 << lev, v2 = (LL)1 << lev + 1;
if(nc > m || nowans > mnv + now + v2 - 1) return 0;
if(lev == -1 || !x) return ans = max(ans, min(nowans + v2 - 1, mnv + now + v2 - 1)), 1;
int cnt = 0;
// 右侧 + -> x = 1
if(nc + sc[s[x][1]] <= m) cnt += dfs(s[x][0], lev - 1, nc + sc[s[x][1]], now + v1, min(mnv, val[s[x][1]]), nowans + v1);
// 左侧 + -> x = 0
if(nc + sc[s[x][0]] <= m) cnt += dfs(s[x][1], lev - 1, nc + sc[s[x][0]], now, min(mnv, val[s[x][0]]), nowans + v1);
if(!cnt)
{
// 右侧 ok -> x = 0
dfs(s[x][0], lev - 1, nc, now, mnv, nowans);
// 左侧 ok -> x = 1
dfs(s[x][1], lev - 1, nc, now + v1, mnv, nowans);
}
return 1;
}
void solve()
{
read(n, m, k);
init();
k --;
for(int i = 1; i <= n; i ++) read(a[i]);
ll sum = 0;
for(int i = 1; i <= n; i ++) read(b[i]), sum += b[i];
if(sum <= m)
{
LL ans = (LL)1 << (k + 3);
for(int i = 1; i <= n; i ++) ans = min(ans, a[i]);
printLL(ans + ((LL)1 << k + 1) - 1);
return;
}
for(int i = 1; i <= n; i ++)
ins(1, k, a[i], b[i]);
ans = 0;
dfs(1, k, 0, 0, (LL)1 << 123, 0);
printLL(ans);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int c, t; read(c, t);
while(t --) solve();
return 0;
}