题目描述

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

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

(trie) $O(nlogs)$

C++ 代码

const int N = 2e4 + 10;
class Solution {

    int son[N*16][2], idx = 0, cnt[N*16];
public:
    int countPairs(vector<int>& nums, int low, int high) {
        for(auto x : nums){
            ist(x);
        }
        return cal(nums, high) - cal(nums, low - 1);
    }

    int cal(vector<int>& nums, int limit){
        int t = 0;
        for(auto x : nums){
            t += qry(x, limit) - 1;
        }
        return t / 2;
    }

    void ist(int x){
        int p = 0;
        for(int i = 15; i >= 0; i--){
            int u = (x >> i) & 1;
            if(son[p][u] == 0) {
                son[p][u] = ++idx;
            }
            cnt[p]++;
            p = son[p][u];
        }
        cnt[p]++;
    }

    int qry(int x, int limit){
        int p = 0;
        int cur = 0;
        int res = 0;
        for(int i = 15; i >= 0; i--){
            int u = (x >> i) & 1;
            if(son[p][u] == 0){
                cur |= (1<<i);
                if(cur > limit) return res;
                else{
                    p = son[p][u^1];
                }
            }
            else if(son[p][u^1] == 0){
                p = son[p][u];
            }
            else{
                if((cur | (1<<i)) <= limit){
                    res += cnt[son[p][u]];
                    p = son[p][u^1];
                    cur |= (1<<i);
                }
                else p = son[p][u];
            }
        }
        return res + cnt[p];
    }
};