CF2093G. Shorten the Array

题意 给定长度为 $n$ 的数组 $a$，从中找出两个数 $a_{i},a_{j}$ 满足 $a_{i}\oplus a_{j} \geqslant k$，并最大化两数距离（即最大化 $j-i+1$），输出这个最大距离。找不到则输出 $-1$。

思路 两数异或最大可以用字典树，但本题有个更好写的做法。

比大小问题，可以转化为判断相等。

给定 $b$，枚举 b += lowbit(b)（其本质是把 $b$ 的一个 0 变 1，低位都变 0）。如果 $a \geqslant b$，那么必然存在一个枚举结果 $b’$，满足 $a$ 同样位数变 0 后与 $b’$ 相同。

比如 $b$ 是 10110，一个数大于等于 $b$，只能是 1011?、11??? 或 1??? 这几种形式。而枚举 b += lowbit(b)，刚好会得到 10110 $\to$ 11000 $\to$ 100000 $\to$ 1000000 $\to$ …… 满足 $a$ 低位都变 0 后与 $b’$ 相同。

这样，我们就把 $a \geqslant b$ 问题转化为判断 32 次 $a’=b’$。

回到本题，只需枚举 k += lowbit(k)，同时把 $a_{i}$ 的低位都变 0，判断是否存在 $a_{i}‘\oplus a_{j}’ = k’$，用桶存下标即可。时间复杂度 $\operatorname{O}(n\log^{2} V)$，$V=10^{9}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 0x3f3f3f3f;

int main() {
    int t;
    cin >> t;

	while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int res = inf;
        if (k == 0) {
            res = 1;
        }
        for (; k > 0; k += (k & -k)) {
            map<int, int> mp;
            for (int i = 0; i < n; i++) {
                int x = a[i] & ~((k & -k) - 1);
                if (mp.count(k ^ x)) {
                    res = min(res, i - mp[k ^ x] + 1);
                }
                mp[x] = i;
            }
        }
        cout << (res == inf ? -1 : res) << endl;
    }

    return 0;
}

练习：2023 山东省赛 J. Not Another Path Query Problem

UPD：上面代码复杂度略高，TLE。可以用 vector 二分代替 map，实现 $\operatorname{O}(n\log n\log V)$ 的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int main() {
    int t;
    cin >> t;

	while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int res = inf;
        if (k == 0) {
            res = 1;
        }
        for (; k > 0; k += k & -k) {
            vector<pair<int, int>> mp(n);
            for (int i = 0; i < n; i++) {
                mp[i].first = a[i] & ~((k & -k) - 1);
                mp[i].second = -i;
            }
            sort(mp.begin(), mp.end());
            for (int i = 0; i < n; i++) {
                int b = a[i] & ~((k & -k) - 1);
                auto it = lower_bound(mp.begin(), mp.end(), pair(b ^ k, -i));
                if (it == mp.end() || it->first != (b ^ k)) {
                    continue;
                }
                int j = -it->second;
                res = min(res, abs(i - j) + 1);
            }
        }
        cout << (res == inf ? -1 : res) << endl;
    }

    return 0;
}