2022-6-11[字典树] 统计异或值在范围内的数对有多少

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。

漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。

输入：nums = [1,4,2,7], low = 2, high = 6
输出：6
解释：所有漂亮数对 (i, j) 列出如下：
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5

输入：nums = [9,8,4,2,1], low = 5, high = 14
输出：8
解释：所有漂亮数对 (i, j) 列出如下：
    - (0, 2): nums[0] XOR nums[2] = 13
    - (0, 3): nums[0] XOR nums[3] = 11
    - (0, 4): nums[0] XOR nums[4] = 8
    - (1, 2): nums[1] XOR nums[2] = 12
    - (1, 3): nums[1] XOR nums[3] = 10
    - (1, 4): nums[1] XOR nums[4] = 9
    - (2, 3): nums[2] XOR nums[3] = 6
    - (2, 4): nums[2] XOR nums[4] = 5

提示：

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 2 * 10^4
• 1 <= low <= high <= 2 * 10^4

struct Trie {
    int cnt;
    vector children;

    explicit Trie() : cnt(0), children(2, nullptr) {};
};

class Solution {
private:
    Trie *root;

    void insert(int val) {
        Trie *node = root;
        for (int i = 15, bit; i >= 0; i--) {
            bit = (val >> i) & 1;
            if (!node->children[bit]) node->children[bit] = new Trie();
            node = node->children[bit];
            node->cnt++;
        }
    }

    int query(int val, int lim) {
        Trie *node = root;
        int result = 0;
        for (int i = 15, bitVal, bitLim; i >= 0 && node != nullptr; i--) {
            bitVal = (val >> i) & 1, bitLim = (lim >> i) & 1;
            result += bitLim && node->children[bitVal] ? node->children[bitVal]->cnt : 0;
            node = node->children[bitVal ^ bitLim];
        }
        return result;
    }

public:
    int countPairs(const vector &nums, int low, int high) {
        int result = 0;
        root = new Trie();
        for (int num:nums) {
            result += query(num, high + 1) - query(num, low);
            insert(num);
        }
        return result;
    }
};

在leetcode题解中看到 hqztrue 大佬的 暴力AC怎么能少得了C++呢？ ，心里想的全是我是菜逼。以下两个代码均来自 暴力AC怎么能少得了C++呢？

#define us unsigned short
us a[20015];

class Solution {
public:
    int countPairs(vector &_a, us l, us r) {
        int n = _a.size(), ans = 0;
        int d = 0;
        for (int i = 0; i < n; ++i) a[i] = _a[i];
        sort(a, a + n);
        for (us *i = a, *end = i + n; i != end; ++i) {
            if (i > a && *i == *(i - 1)) {
                ans += d;
                continue;
            }
            us *j = i + 1, *end1 = end - 8;
            d = 0;
            for (; j < end1; j += 8) {
                us x = *i ^ *j, x1 = *i ^ *(j + 1), x2 = *i ^ *(j + 2), x3 = *i ^ *(j + 3), x4 = *i ^ *(j + 4), x5 = *i ^ *(j + 5), x6 = *i ^ *(j + 6), x7 = *i ^ *(j + 7);
                d += (x >= l && x <= r) + (x1 >= l && x1 <= r) + (x2 >= l && x2 <= r) + (x3 >= l && x3 <= r) + (x4 >= l && x4 <= r) + (x5 >= l && x5 <= r) + (x6 >= l && x6 <= r) + (x7 >= l && x7 <= r);
            }
            for (; j < end; ++j) d += (*i ^ *j) >= l && (*i ^ *j) <= r;
            ans += d;
        }
        return ans;
    }
};

#include

#define us unsigned short
const int N = 20005, U = 31;
us a[N] __attribute__((aligned(64)));

class Solution {
public:
    __attribute__((no_sanitize_address, no_sanitize_memory))
    __attribute__((target("avx512bw")))
    int countPairs(vector &_a, us l, us r) {
        int n = _a.size(), ans = 0, d = 0;
        for (int i = 0; i < n; ++i)a[i] = _a[i];
        sort(a, a + n);
        __m512i L = _mm512_set1_epi16(l), R = _mm512_set1_epi16(r);
        for (int i = 1; i < n; ++i) {
            if (a[i] != a[i - 1]) {
                us x = a[i];
                __m512i X = _mm512_set1_epi16(x);
                d = 0;
                for (__m512i *I = (__m512i *) a, *end = (__m512i *) (a + (i & ~U)); I != end; ++I) {
                    __m512i Y = _mm512_xor_si512(X, *I);
                    d += __builtin_popcount(_mm512_cmpge_epi16_mask(Y, L) & _mm512_cmple_epi16_mask(Y, R));
                }
                for (int j = i & ~U; j < i; ++j) {
                    int y = x ^ a[j];
                    d += y >= l && y <= r;
                }
            }
            ans += d;
        }
        return ans;
    }
};