5640. 与数组中元素的最大异或值

5640. 与数组中元素的最大异或值

第221场周赛t4
trie树
其中要求<=m的条件，就把nums和queries排序，每次插入的nums[i]，都保证<=m。保留下queries中的位置信息pos

typedef pair<int,int> pii;
class Solution {
public:
    int trie[100010 * 32][2],idx;
    void insert(int x){
        int p=0;
        for(int i=30;i>=0;i--){
            // 确定分支
            int u=x>>i&1;
            if(!trie[p][u])trie[p][u]=++idx;
            p=trie[p][u];
        }
    }
    int search(int x){
        int p=0,res=0;
        for(int i=30;i>=0;i--){
            int u=x>>i&1;
            if(trie[p][u^1]){
                p=trie[p][u^1];
                res+=1<<i;
            }else p=trie[p][u];
        }
        return res;
    }
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& q) {
        idx=0;
        memset(trie,0,sizeof trie);

        sort(nums.begin(),nums.end());
        int n=q.size();
        vector<pair<pii,int>>qs(n);
        for(int i=0;i<n;i++){
            // x,m
            qs[i]={{q[i][0],q[i][1]},i};
        }
        sort(qs.begin(),qs.end(),[](pair<pii,int>&a,pair<pii,int>&b){
            return a.first.second<b.first.second;
        });
        int ind=0;
        vector<int>res(n);
        for(int i=0;i<qs.size();i++){
            int x=qs[i].first.first;
            int m=qs[i].first.second;
            int pos=qs[i].second;
            while(ind<nums.size() && nums[ind]<=m){
                insert(nums[ind]);
                ind++;
            }
            int ans;
            if(ind==0) ans=-1;
            else ans=search(x);
            res[pos]=ans;
        }

        return res;
    }
};