xor 题解
前言
这里是 2024 年 3 月 2 日，我小小的愿望终结的地方。
后来，我计算出了能够使得自己进入省队的 day1 最低得分：恰好是 100 。也就是说，我只需要在 day 1 的考场上过掉任何一道题，就能够进入当年的省队。即使我采取了先开 T2 的激进策略而没有写出 T1 也行。
退役以后没有再碰过需要这么长时间和这么巨大精力的题目，但是在我的印象中，那年的 D1T2 明明非常简单。让我有自信在足够短的时间内把它拿下。但是比赛进行到 2.5h 左右的时候不知什么原因我的大脑突然开始空白，完全忘记了自己代码的含义，从而带崩了整场省选，那年奇迹的进度也永远停留在了 99%。
漫长的时光过去，我和流转的日月相对无言。
而现在，拂过同一间教室的春风提醒我，也许回到那个记忆封印的地方，才能继续写下新的故事。
好了，希望你把上面的这段话忘掉，我们开始做题吧。
思路
暴力
前面的部分分全都没用，直接做 \(O(nk^2)\)。
首先判掉可以全部选择定向加强的方案，二分答案，思考怎么 check。
首先，选择的 \(x\) 必须保证 \(\min a_i + x \geq mid\)，这样至少被定向加强的 \(a_i\) 是合法的，其他的 \(a_i\) 也要满足这个充分不必要条件。
对于任何一个 \(i\) ，使得 \(a_i \oplus x \geq mid\) 的 \(x\) 在数轴上构成 \(O(k)\) 段区间。这些区间内需要花费的体力值可以减去 \(b_i\) ，当 \(x\) 落在这些区间时，是不需要定向加强的。
注意到这个合法区间一定可以用 Trie 树（或者理解为大小为 \(2^k\) 的动态开点线段树）上的一个点表示，那么直接修改的复杂度就是 \(O(nk^3)\)，最后检查一遍树上的每个点的体力值是否合法，以及这个点能否满足 \(\min a_i + x \geq mid\) ，已经能通过测试点 14,15 得到非平凡分数了。
然后发现这 \(O(k)\) 个区间可以在一次 DFS 中全部修改好，这样就做到 \(O(nk^2)\)。不知道为什么，这个做法常数很大，只能额外通过 C 性质的 11~13 号测试点，无语了。
正解
那么正解也很显然是要干掉外面的二分，我们希望能够 按位确定答案。
每次尝试在当前二进制位填上 1，不能的话就改回 0。
这样一次 check 仍然是 \(\Theta(nk)\) 的。但是我们可以发现，我们干了大量重复的工作。在确定较小的位的时候，较高位的 Trie 根本没有必要改动。也就是说，我们采用 BFS 建立 Trie，每填上答案的一位，往下扩展一层。
需要注意的是，由于我们建立高位的 Trie 的时候，有可能会改动 ans，所以当 ans 改动之后我们还需要根据 ans 改动的结果修改一些加法标记。在进入下一层之前也需要撤销部分操作。
有的没的
在济南之旅后，又过了太长没有被感动过的时光，我徘徊许久，但最终一步也没能迈出。
错过的机会不会再有，但破碎的记忆中一定还有崭新的故事。仅仅因为见证过，所以我相信，永不长大的故事还可以在这里继续。
我真心这样祈愿。
code
#include<bits/stdc++.h>
#define ll1 (__int128)1
using namespace std;
const int N = 5e5+5, M = N * 61;
typedef __int128 ll;
void read(__int128 &x){// read a __int128 variablechar c; bool f = 0;while(((c = getchar()) < '0' || c > '9') && c != '-');if(c == '-'){f = 1; c = getchar();}x = c - '0';while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';if(f) x = -x;
}void read(int &x){// read a __int128 variablechar c; bool f = 0;while(((c = getchar()) < '0' || c > '9') && c != '-');if(c == '-'){f = 1; c = getchar();}x = c - '0';while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';if(f) x = -x;
}void write(__int128 x){// print a __int128 variableif(x > 9)write(x / 10);putchar(x % 10 + '0');
}int c, T;
int n, m, k, b[N];
ll a[N], tag[M], ans, val[M], S;
int u[N];
int ch[2][M], cnt, idx, flag, root;void ins() {ans = 0;ch[0][1] = ch[1][1] = 0;for(int i = 1; i <= n; i++) {u[i] = 1;//at root;}cnt = 1;int lstcnt = 1;ll mx = 0;for(int bit = k - 1; bit >= 0; bit--) {lstcnt = cnt;ans += (ll1 << bit);ll V = 0, mx2 = 0;for(int id = 1; id <= n; id++) {V = max(V, ans - a[id]);bool C = !((a[id] >> bit) & 1);if(!ch[C][u[id]]) {ch[C][u[id]] = ++cnt;tag[cnt] += tag[u[id]];ch[0][cnt] = ch[1][cnt] = 0;}tag[ch[C][u[id]]] += b[id];if(ch[0][u[id]]) {val[ch[0][u[id]]] = val[u[id]];}if(ch[1][u[id]]) {val[ch[1][u[id]]] = val[u[id]] + (ll1 << bit);}if(S - tag[ch[C][u[id]]] <= m) {mx2 = max(mx2, (val[ch[C][u[id]]] + (ll1 << bit) - 1));}}if(max(mx, mx2) < V) {ans -= (ll1 << bit);//bit = -1, actually in the layer 0.}for(int id = 1; id <= n; id++) {bool t = !((ans >> bit) & 1), s = !((a[id] >> bit) & 1), C2 = t ^ s;tag[ch[s][u[id]]] -= b[id];if(t) {if(!ch[s][u[id]]) ch[s][u[id]] = ++cnt, tag[cnt] += tag[u[id]], ch[0][cnt] = ch[1][cnt] = 0;tag[ch[s][u[id]]] += b[id];}if(!ch[C2][u[id]]) {ch[C2][u[id]] = ++cnt, tag[cnt] += tag[u[id]], ch[0][cnt] = ch[1][cnt] = 0;}if(ch[0][u[id]]) {val[ch[0][u[id]]] = val[u[id]];}if(ch[1][u[id]]) {val[ch[1][u[id]]] = val[u[id]] + (ll1 << bit);}u[id] = ch[C2][u[id]];}for(int i = lstcnt + 1; i <= cnt; i++) {if(S - tag[i] <= m) {mx = max(mx, (val[i] + (ll1 << bit) - 1));}}}
}void solve() {for(int i = 1; i <= n; i++) {read(a[i]);}S = 0;for(int i = 1; i <= n; i++) {read(b[i]), S += b[i];}if(S <= m) {write((*min_element(a + 1, a + n + 1)) + (ll1 << k) - 1);puts("");return;}for(int i = 0; i <= cnt; i++) {tag[i] = 0;}cnt = idx = 0, root = 0;ins();write(ans);puts("");
}int main(){scanf("%d %d", &c, &T);while(T--) {scanf("%d %d %d", &n, &m, &k);solve();}return 0;
}
后来有一天 能再见面 不知是何年
回忆太重 伤痕太痛 不希望你懂
当岁月将 我们分割 渡不同的河
话说不出口 就来唱首歌 这应该会有用