//
// Created by 罗炳国 on 2023/7/20.
//

#ifndef PFJ_CODE09_MAXIMIZEXOR_H
#define PFJ_CODE09_MAXIMIZEXOR_H

#include "commonHeader.h"

/**
 * 给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
 第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，
 其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
 返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

 示例 1：
 输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
 输出：[3,3,7]
 解释：
 1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
 2) 1 XOR 2 = 3.
 3) 5 XOR 2 = 7.

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/maximum-xor-with-an-element-from-array
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

struct node {
    int minVal;
    node *next[2];
    node() {
        for (int i = 0; i < 2; i++)
            next[i] = nullptr;
        minVal = INT32_MAX;
    }
};

class numTrie {
public:
    void add(int num) {
        node *cur = &head;
        head.minVal = min(num, head.minVal);
        for (int off = 30; off >= 0; off--) {
            int path = (num >> off) & 1;
            if (cur->next[path] == nullptr)
                cur->next[path] = new node;
            cur->next[path]->minVal = min(cur->next[path]->minVal, num);
            cur = cur->next[path];
        }
    }

    int maxXor(int num, int limit) {
        int ans = 0;
        node *cur = &head;

        for (int off = 31; off >= 0; off--) {
            int path = (num >> off) & 1;
            int best = path ^ 1;
            if (cur->next[best] == nullptr || cur->next[best]->minVal > limit)
                best ^= 1;
            if (cur->next[best]->minVal > limit)
                return -1;
            ans |= (best ^ path) << off;
            cur = cur->next[best];
        }
        return ans;
    }

private:
    node head;
};


class code09_maximizeXor {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> ans;
        numTrie trie;

        for (auto &val : nums)
            trie.add(val);

        for (auto &pairs : queries)
            ans.push_back(trie.maxXor(pairs[0], pairs[1]));
        return ans;
    }
};

#endif //PFJ_CODE09_MAXIMIZEXOR_H