二维偏序问题

========>二维偏序知识讲解

  LeetCode第349场周赛T4 《最大和查询》

  二维偏序模板题。把 (a[i], b[i]) 看成二维平面上的一个红点，(q[i][0], q[i][1]) 看成二维平面上的一个蓝点。我们要对每个蓝点求出它的右上方横纵坐标之和最大的红点。

  我们将所有点先按横坐标从大到小排序，然后依此枚举每个点。这样遇到一个蓝点 (x, y)，我们只要求之前枚举过的，且纵坐标大于等于 y 的红点中，横纵坐标之和最大是多少。用树状数组维护即可。复杂度 O(nlog⁡n)。

  因为 a，b 和 q 里面的数很大，但是我们只关心数的相对大小关系，因此先把所有数离散化再计算（当然，离散化之前要把 a[i] + b[i] 的值存起来）。

typedef pair<int, int> PII;
typedef pair<PII, int> PPI;
#define x first
#define y second
class Solution {
public:
    vector<int> z;
    int tr[300010];
    int lowbit(int x) {return x & -x;}

    void modify(int u, int v){
        for(int i = u; i <= z.size(); i += lowbit(i)){
            tr[i] = max(tr[i], v);
        }
    }

    int query(int u){
        int ans = -1;
        for(int i = u; i; i -= lowbit(i)){
            ans = max(ans, tr[i]);
        }
        return ans;
    }

    int find(int x){
        int l = 1, r = z.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(z[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    vector<int> maximumSumQueries(vector<int>& a, vector<int>& b, vector<vector<int>>& q) {
        int n = a.size(), m = q.size();
        z.push_back(-1);
        for(int i = 0; i < n; i++){
            z.push_back(a[i]), z.push_back(b[i]);
        }
        for(int i = 0; i < q.size(); i++){
            z.push_back(q[i][0]), z.push_back(q[i][1]);
        }
        sort(z.begin(), z.end());
        z.erase(unique(z.begin(), z.end()), z.end());
        vector<int> res(m);
        vector<PPI> t;
        int lz = z.size();
        //离散化并且坐标大小关系反转，为了用树状数组维护前缀来求最值问题
        //注意相同的坐标点，实际点要在查询点前面，这样用树状数组才是正确的
        for(int i = 0; i < n; i++){  
            int x = lz - find(a[i]), y = lz - find(b[i]);
            t.push_back({{x, y}, -(a[i] + b[i])});
        }
        for(int i = 0; i < m; i++) {
            int x = lz - find(q[i][0]), y = lz - find(q[i][1]);
            t.push_back({{x, y}, i});
        }
        //排序,按照x坐标从小到大，然后二位偏序，另一维用树状数组维护
        sort(t.begin(), t.end());
        memset(tr, -1, sizeof tr);
        int sz = t.size();
        for(int i = 0; i < sz; i++){
            int x = t[i].x.x, y = t[i].x.y, v = t[i].y;
            if(v < 0) modify(y, -v);   //实际点
            else res[v] = query(y);  //查询点
        }
        return res;
    }
};