1803. 統計異或值在範圍内的數對有多少

周賽題解

• 題目大意：
• 思路分析
• • 閑扯
  • 思路
• AC代碼(帶注釋,友善複習)

題目大意：

統計異或值在範圍内的數對有多少

給你一個整數數組 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

• 資料範圍

1 <= nums.length <= 2 * 104

1 <= nums[i] <= 2 * 104

1 <= low <= high <= 2 * 104

思路分析

閑扯

這道題給人的第一感覺就是直接暴力枚舉，一看資料範圍就知道還是刷題不夠，這個2e4範圍明顯不能暴力枚舉，賽後聽群裡大佬說用Trie樹，雖然知道Trie樹的基本用法，但還是不會bushi,看了題解才發現隻會用Trie樹求最大異或對是遠遠不夠的

思路

• 我們使用Trie樹來存儲 (1-i-1) 的所有數，第i個數為x，這裡采用邊插入邊查詢，即每次插入x之前查詢 (1-i-1) 中滿足與x異或在範圍内的，是以需要開辟的空間為：O(NlogS)
• 查詢操作的時候如何查找初符合x^u在範圍内的數量是這道題的難點，可以采用字首和的思想:找出 x ^ u<=high的u的數量r,滿足 x ^u <=low-1 的數量l,則對于插入的第i個數，1-i-1 中滿足的數為: r-l
• 問題轉化為求x ^u<=limit 的u的個數，這種寫法我一直wa掉，最後借鑒了大佬的<limit 的寫法，這樣寫法很簡明，以後建議使用
• 具體的Trie樹操作可以去了解一下，這個資料結構處理異或的一些操作很有效

AC代碼(帶注釋,友善複習)

class Solution {
public:
    static const int N=20010*20;
    int tr[N][2],cnt[N],idx=0;
    void insert(int x)
    {
        int p=0;
        for(int i=16;i>=0;i--){
            int u=x>>i&1;
            if(!tr[p][u]) tr[p][u]=++idx;
            p=tr[p][u];
            cnt[p]++;
        }
    }
    int query(int x,int limit)
    {
        int p=0;
        int res=0;
        for(int i=16;i>=0;i--){
            int u=x>>i&1,v=limit>>i&1;
            //這種寫法可以發現res累加的都是異或後小于limit的,等于的都沒有選擇，是以limit的範圍要大一
            //因為每次有兩種選擇時，我都是目前的cur與limit相等，
            //是以每次累加的都是異或後<limit的，最後統計的總和也是異或後小于limit的，
            if(u == 0 && v == 0) p = tr[p][0];
            else if(u == 0 && v == 1) res += cnt[tr[p][0]], p = tr[p][1];
            else if(u == 1 && v == 0) p = tr[p][1];
            else if(u == 1 && v == 1) res += cnt[tr[p][1]], p = tr[p][0];
            if(!p) break;
        }
        return res;
    }
    int countPairs(vector<int>& nums, int low, int high) {
        int res = 0;
        for(auto &x : nums) {
        //這裡要先查詢在插入，因為x^x =0也是滿足的
            res += query(x, high+1) - query(x, low);
            insert(x);
        }
        return res;
    }
};