【Codeforces】1658D2 388535 (Hard Version)题解

题目大意

给定两个数 $l, r$（$0 < l \le r \le 2^{17}$），将 $[l, l+1, \ldots, r-1, r]$ 的一个任意排列全部异或 $x$，得到一个新的数组 $a$。

给定 $l, r$ 和 $a$ 数组，求 $x$。

题目链接

思路

简单版本的做法如下：

按位处理，计算异或前的数组每一位 $1$ 的个数，设为 $cntA$，计算异或后的数组每一位 $1$ 的个数，记为 $cntB$。

1. 一旦 $cntA_i \ne cntB_i$，$x$ 这一位一定为 $1$。
2. 如果 $cntA_i = cntB_i$，$x$ 这一位可以为 $1$，也可以为 $0$。

因为 $l = 0$，所以 2 总是成立：异或后的数组一定有一个 $x$（异或前有个 $0$），所以 $x$ 某一位为 $1$，那么异或后的数这一位 $1$ 的数量一定会变化。

而一旦 $l \ne 0$，就有可能 $1 \to 0$ 和 $0 \to 1$ 的数量相同而抵消，比如 $[1, 2] \oplus 2 = [0, 3]$，前后每一位 $1$ 的数量都相同。

所以我们不能再按照之前的思路。

答案一定存在于 $l \oplus a_i$（$1 \le i \le n$）中，逐一验证 $l \oplus a_i$ 是否为答案。

那么如何验证呢？验证 $x \oplus a_i$ 的结果，最大值是否为 $r$，最小值是否为 $l$。

求一些数异或一个值的最大最小值，这个问题可以用 trie 树解决。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int maxN = 1e5 + 7;

int T, l, r, cnt1[53], cnt2[53];

inline void calc(int *cnt, int x)
{
    int now = 0;
    while(x) {
        if(x & 1)
            cnt[now]++;
        now++; x >>= 1;
    }
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        memset(cnt1, 0, sizeof cnt1);
        memset(cnt2, 0, sizeof cnt2);
        scanf("%d%d", &l, &r);
        for(int i = l; i <= r; ++i) {
            calc(cnt1, i);
            int x; scanf("%d", &x);
            calc(cnt2, x);
        }
        int ans = 0;
        for(int i = 0; i < 31; ++i)
            if(cnt1[i] != cnt2[i])
                ans |= (1 << i);
        printf("%d\n", ans);
    }
    return 0;
}