算法数据结构

二维偏序问题：扫描线+树状数组

字数统计: 2.1k字   |   阅读时长: 9分
,

摘要: 一个维度用扫描线（排序）保证有序；一个维度用树状数组保证有序；维护权值的最值

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

二维偏序问题

形式化定义

如果形式化地定义，二维偏序问题的描述如下。

$X$ 为一个非空集合，$R$ 是定义在 $X$ 上的具有自反，反对称，传递的二元关系，称 $P = (X, R)$ 为一个偏序集，$R$ 为偏序关系。

给定偏序集 $X$ 中的 $n$ 个元素组成的集合 $x_{1}, x_{2}, \cdots, x_{n}$，现在给定一个 $x_{i}$，问 $X$ 中满足 $x_{j} < x_{i}$ 的元素 $x_{j}$ 的数量有多少。这里的 $< $ 指偏序关系 $R$。

当 $x_{i}$ 为二维有序数对 $(a_{i}, b_{i})$ 时，以上问题即为二维偏序问题。

当 $x_{i}$ 为三维有序数对 $(a_{i}, b_{i}, c_{i})$ 时，以上问题即为三维偏序问题。

直观理解

二维偏序问题直观上可以理解为平面点集上的数点问题。也就是首先给定一个平面点集，此后一次查询指定一个矩形范围，问矩形范围内的点有多少个。

二维偏序问题

也可以给点集中的每个点指定一个权值，这样在查询时，可以问矩形范围内的点的权值之和/权值的最值。解法差不多。

解决这种二维偏序问题的主流数据结构有树状数组/线段树、KD树，如果用 CDQ 分治，可以解决更高维的偏序问题。

本文我们用扫描线+树状数组的方式解决查询权值最值的二维偏序问题。

题目

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
2
3
4
5
6
7
8
9
nums1.length == nums2.length 
n == nums1.length 
1 <= n <= 1e5
1 <= nums1[i], nums2[i] <= 1e9 
1 <= queries.length <= 1e5
queries[i].length == 2
xi == queries[i][1]
yi == queries[i][2]
1 <= xi, yi <= 1e9

示例 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 。因此，不存在答案。

算法：扫描线+树状数组

将点集以及所有查询的有序数对按照横坐标升序排序，当横坐标相同时，查询的点放排前面，点集中的点排后面，然后倒序枚举。

这样当枚举到某个查询 $(x, y)$ 的时候，此前已经枚举过的点集中的点都是横坐标大于等于 $x$ 的。

因此只需要有某种数据结构维护已经枚举的点集中的点，能够支持高效查询当纵坐标大于等于 $y$ 时，点的横纵坐标之和的最大值即可。这正是区间最值查询问题，可以用树状数组解决。

综上分析，完整算法如下。

(1) 根据 nums1, nums2 数组，以及 queries 数组，构造维护扫描线算法的事件数组 events，事件（点集点和查询点）定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Point
{
    int x;
    int y;
    int s; // 1: 点集; 0: 查询
    Point(){}
    Point(int x, int y):x(x),y(y){}
    bool operator<(const Point& p) const
    {
        if(x == p.x)
            return s < p.s;
        return x < p.x;
    }
};

(2) 将 nums2 以及 queries[i][1] 的所有值离散化，初始化维护最大值的树状数组。

(3) 将 events 升序排序，然后倒序枚举：

  • 如果枚举到点集点 $(x, y)$，将 $y$ 离散化后的值 $find(y)$ 作为下标，若 bit.query(find(y), find(y)) < x+y，则将树状数组中 $find(y)$ 位置的值更新为 $x+y$，
  • 如果枚举到查询点 $(x, y)$，将 $y$ 离散化后的值 $find(y)$ 作为查询下标，查询树状数组在 $[find(y), find(INF)]$ 上的最大值作为答案返回。

代码 (C++)

离散化和树状数组的代码模板分布参考文章 离散化 和 树状数组：单点修改，区间最值查询，这里没有修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

class BIT_RMQ
{
public:
    BIT_RMQ():vec(1,-2),a(1,-2){}
    BIT_RMQ(int n):vec(n + 1, -2),a(n,-2){}

    void update(int idx, int x)
    {
        // vec[idx] 管的是 [idx-lowbit[idx] + 1..idx] 这个区间
        // a[idx -  1] 改为 x
        // vec[idx]
        a[idx - 1] = x;
        vec[idx] = x;
        int n = a.size();
        for(int i = idx; i <= n; i += _lowbit(i))
        {
            for(int j = 1; j < _lowbit(i); j <<= 1)
            {
                // j < _lowbit(i) <= j - i < _lowbit(i) - i <= i - j > i - _lowbit(i)
                // i = 8，即改 vec[8]
                // 要看 vec[7] = i - 1
                //      vec[6] = i - 2
                //      vec[4] = i - 4
                vec[i] = max(vec[i], vec[i - j]);
            }
        }
    }

    int query(int l, int r)
    {
        // 直接看 vec[r] 不行
        // vec[r] 对应 [r - lowbit[r] + 1, r]
        int ans = a[r - 1];
        while(true)
        {
            ans = max(ans, a[r - 1]);
            if(l == r)
                break;
            --r;
            for(; r - _lowbit(r) >= l; r -= _lowbit(r))
                ans = max(ans, vec[r]);
        }
        return ans;
    }

    void view()
    {
        int n = a.size();
        for(int i = 0; i < n; ++i)
            cout << a[i] << " ";
        cout << endl;
        for(int i = 1; i <= n; ++i)
            cout << vec[i] << " ";
        cout << endl;
    }

private:
    vector<int> vec;
    vector<int> a;

    int _lowbit(int x)
    {
        return x & (-x);
    }
};


struct Point
{
    int x;
    int y;
    int q; // >= 0: 查询的下标; -1: 点集
    Point(){}
    Point(int x, int y, int q):x(x),y(y), q(q){}
    bool operator<(const Point& p) const
    {
        if(x == p.x)
            return q > p.q;
        return x < p.x;
    }
};

int _find(int v, const vector<int>& aa) // 从 nums 的值找到对应的离散化之后的值
{
    return lower_bound(aa.begin(), aa.end(), v) - aa.begin() + 1;
}

vector<int> discretization(const vector<int>& a)
{
    int n = a.size();
    vector<int> aa = a;
    sort(aa.begin(), aa.end());
    aa.erase(unique(aa.begin(), aa.end()), aa.end());
    return aa;
}

class Solution {
public:
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size();
        int m = queries.size();
        vector<Point> events(n + m);
        for(int i = 0; i < n; ++i)
        {
            events[i].x = nums1[i];
            events[i].y = nums2[i];
            events[i].q = -1;
        }
        for(int i = 0; i < m; ++i)
        {
            events[n + i].x = queries[i][0];
            events[n + i].y = queries[i][1];
            events[n + i].q = i;
        }

        const int INF = 1e9;
        vector<int> ys(n + m + 1);
        for(int i = 0; i < n; ++i)
            ys[i] = nums2[i];
        for(int i = 0; i < m; ++i)
            ys[n + i] = queries[i][1];
        ys[n + m] = INF;
        vector<int> idx = discretization(ys);

        BIT_RMQ bit_rmq(idx.size());
        bit_rmq.update(_find(INF, idx), -1);

        sort(events.begin(), events.end());
        vector<int> result(m);
        for(int i = n + m - 1; i >= 0; --i)
        {
            Point e = events[i];
            if(e.q == -1)
            {
                if(bit_rmq.query(_find(e.y, idx), _find(e.y, idx)) < e.x + e.y)
                    bit_rmq.update(_find(e.y, idx), e.x + e.y);
            }
            else
            {
                result[e.q] = bit_rmq.query(_find(e.y, idx), _find(INF, idx));
            }
        }
        return result;
    }
};
Share