最大和查询

题目

2736. 最大和查询

---

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。

返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
输出：[6,10,7]
解释：
对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。
因此，我们返回 [6,10,7] 。

示例 2：

输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出：[9,9,9]
解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。

示例 3：

输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
输出：[-1]
解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。

提示：

• nums1.length == nums2.length 
• n == nums1.length 
• 1 <= n <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^9 
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• xi == queries[i][1]
• yi == queries[i][2]
• 1 <= xi, yi <= 10^9

题解

方法一：

思路

离线处理查询，将查询按照x相等则y大的排在前面，x不相等则x大的排前面进行排序。

遍历排序后的查询，设当前查询为(x,y)，那么我们将所有(nums1[i], nums2[i])的点对中nums1[i]>=x的nums2[i]作为键以及nums1[i]+nums[j]作为值加入到树状数组中。这样就可以用树状数组求出大于等于y的最大值以作为当前查询的答案。

这里有几个细节问题需要解决。

首先num2[i]最大值可达1e9，不能直接作为树状数组的索引。但是nums1 nums2 queries大小均不超过1e5, 我们可以对所有值进行离散化，再将离散化后的nums2[i]可以作为树状数组的键。

此外，树状数组的基本功能可以做到单点修改，前缀求和。稍微修改可以求前缀的最大值。但是本题要求后缀的最大值（大于等于y的最大值）。我们可以用索引N-i替代索引i，反转了索引大小关系。这里N为树状数组大小。

代码

class Solution {
public:
    #define N 400004
    int a[N];
    int ask(int x) {
        int rt = -1;
        for (int i=x; i; i-=i&-i) {
            rt = max(rt, a[i]);
        }
        return rt;
    }
    void add(int x, int val) {
        for (int i=x; i<N; i+=i&-i) {
            a[i] = max(a[i], val);
        }
    }
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        memset(a, -1, sizeof(a));
        map<int,int> mp;
        for (int i:nums1) mp[i];
        for (int i:nums2) mp[i];
        for (auto i:queries) mp[i[0]], mp[i[1]];
        int c = 1;
        for (auto& [i,j]:mp) j = c++;
        int n = nums1.size();
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            if (nums1[a] == nums1[b]) return nums2[a] > nums2[b];
            return nums1[a] > nums1[b];
        });
        int qn = queries.size();
        vector<int> qidx(qn);
        iota(qidx.begin(), qidx.end(), 0);
        sort(qidx.begin(), qidx.end(), [&](int a, int b) {
            return queries[a][0] > queries[b][0];
        });
        vector<int> ans(qn);
        int p = 0;
        for (int i:qidx) {
            // cout << i << " " <<queries[i][0] << " " << queries[i][1] << "\n";
            int x = mp[queries[i][0]], y = mp[queries[i][1]];
            while (p<n && mp[nums1[idx[p]]]>=x) {
                // cout << nums1[idx[p]] << " " << nums2[idx[p]] << "\n";
                add(N-mp[nums2[idx[p]]], nums1[idx[p]]+nums2[idx[p]]);
                p++;
            }
            ans[i] = ask(N-y);
        }
        return ans;
    }
};

一种比较优雅的实现方式，将查询二元组和点对二元组合并到一个三元组数组中，其中三元组第三关键字作为区分查询和点对的标志。

class Solution {
public:
    #define N 400004
    int a[N];
    int ask(int x) {
        int rt = -1;
        for (int i=x; i; i-=i&-i) {
            rt = max(rt, a[i]);
        }
        return rt;
    }
    void add(int x, int val) {
        for (int i=x; i<N; i+=i&-i) {
            a[i] = max(a[i], val);
        }
    }
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        memset(a, -1, sizeof(a));
        map<int,int> mp;
        for (int i:nums1) mp[i];
        for (int i:nums2) mp[i];
        for (auto i:queries) mp[i[0]], mp[i[1]];
        int c = 1;
        for (auto& [i,j]:mp) j = c++;
        vector<tuple<int,int,int>> a;
        int n = nums1.size();
        for (int i=0; i<n; i++) {
            a.emplace_back(mp[nums1[i]], mp[nums2[i]], i+1);
        }
        int qn = queries.size();
        for (int i=0; i<qn; i++) {
            a.emplace_back(mp[queries[i][0]], mp[queries[i][1]], -i);
        }
        sort(a.rbegin(), a.rend()); // 三元组字典序降序排序
        vector<int> ans(qn);
        for (auto [i,j,k]:a) {
            if (k > 0) {
                add(N-j, nums1[k-1] + nums2[k-1]);
            } else {
                ans[-k] = ask(N-j);
            }
        }
        return ans;
    }
};