二维偏序

概念

偏序关系满足：

  1. 反自反性（Reflexivity）： 对于集合中的每个元素，关系都与自身存在。
  2. 反对称性（Antisymmetry）： 如果存在a<=b && b<=a，则必须是a==b
  3. 传递性（Transitivity）： 如果存在a<=b && b<=c，则必须是a<=c

二维偏序问题涉及对一个二维数据集中元素的排序，其中排序不仅仅依赖于元素自身的大小关系，还可能依赖于元素在不同维度上的关系。

二维偏序是这样一类问题：已知点对的序列(a1,b1), (a2,b2), (a3,b3)...，
并在其上定义某种偏序关系<，现有点(ai,bi)，求满足(aj,bj) < (ai,bi)的的数量。

二维偏序问题一般是要使其中的一个维度有序，再通过树状数组的方式处理另一个维度

翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

1
2
输入: [1,3,2,3,1]
输出: 2

示例 2:

1
2
输入: [2,4,3,5,1]
输出: 3

注意:

  1. 给定数组的长度不会超过50000。
  2. 输入数组中的所有数字都在32位整数的表示范围内。

树状数组

题目要求的第一个维度：i < j，我们只要按顺序（或者逆序）遍历数组，那么这个维度就已经是有序的，不需要处理了。
所以我们考虑第二个维度，我们使用树状数组add之前出现过的数nums[i]，用query获取满足nums[i] > 2*nums[j]条件的数

（ps：这题的条件似乎并不满足偏序的第一个性质：反自反性，但是很适合这样的解法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class FenwickTree {
    int[] tr;  // [1, n]
    public FenwickTree(int n) {  // [0, n-1]
        this.tr = new int[n+1];
    }
    public int lowbit(int x) {
        return x & (-x);
    }
    public void add(int i, int val) {
        while (i < tr.length) {
            tr[i] += val;
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += tr[i];
            i -= lowbit(i);
        }
        return res;
    }
}

如果是顺序遍历数组，那么我们就按照nums[i] > 2*nums[j]条件query即可，这里求的就是后缀了。同时注意这里因为乘2，所以需要用Long保存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length, res = 0;
        TreeSet<Long> set = new TreeSet<>(); 
        for (int i = 0; i < n; i++) {
            set.add((long)nums[i]);
            set.add(2L*nums[i]);
        }
        int idx = 0;
        Map<Long, Integer> map = new HashMap<>();
        for (Long x : set) map.put(x, ++idx);
        FenwickTree tr = new FenwickTree(set.size());
        for (int i = 0; i < n; i++) {
            res += tr.query(set.size()) - tr.query(map.get(2L*nums[i]));
            tr.add(map.get((long)nums[i]), 1);
        }
        return res;
    }
}

如果是逆序遍历数组，那么query的条件就是nums[j] < nums[i]/2，需要注意这里除2的取整问题，正数除2是向下取整，负数除2是向上取整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length, res = 0;
        TreeSet<Integer> set = new TreeSet<>(); 
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
            set.add(nums[i]/2);
            set.add(nums[i]/2-1);
        }
        int idx = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer x : set) map.put(x, ++idx);
        FenwickTree tr = new FenwickTree(set.size());
        // 从右到左考虑，就是nums[j] < nums[i]/2，这里正负数除以2取整，就需要考虑正负数取整方向不一致问题
        // 比如3/2 = 1，3是向下取整；而-3/2 = -1，-3是向上取整
        for (int i = n-1; i >= 0; i--) {
            if (nums[i] >= 0 && nums[i] % 2 == 1) idx = nums[i]/2;  // nums[i]=1 -> nums[j]=0
            else idx = nums[i]/2 - 1;  // nums[i]==2 -> nums[j]=0; nums[i]=-1 -> nums[j]=-1; nums[i]=-2 -> nums[j]=-2
            res += tr.query(map.get(idx));
            tr.add(map.get(nums[i]), 1);
        }
        return res;
    }
}

最大和查询

给你两个长度为 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：

1
2
3
4
5
6
7
输入：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：

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

示例 3：

1
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

排序+树状数组

这题就需要先排序来确保第一个维度是有序的，再通过树状数组处理第二个维度

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
class FenwickTree {
    int[] tr;  // [1, n]
    public FenwickTree(int n) {  // [0, n-1]
        this.tr = new int[n];
        Arrays.fill(tr, -1);
    }
    public int lowbit(int x) {
        return x & (-x);
    }
    public void add(int i, int val) {
        while (i < tr.length) {
            tr[i] = Math.max(tr[i], val);
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int res = -1;
        while (i > 0) {
            res = Math.max(res, tr[i]);
            i -= lowbit(i);
        }
        return res;
    }
}
class Solution {
    /**
    二维偏序的一般解决方法是排序一维，用数据结构处理第二维（这种数据结构一般是树状数组）
    */
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int m = queries.length, n = nums1.length, res[] = new int[m];
        Arrays.fill(res, -1);
        Integer qidxs[] = new Integer[m], idxs[] = new Integer[n];
        Arrays.setAll(qidxs, i -> i);
        Arrays.setAll(idxs, i -> i);
        // 设queries[i][0]为x，queries[i][1]为y
        // 把nums1和x都从大到小排序
        Arrays.sort(idxs, (j, i) -> nums1[i] - nums1[j]);
        Arrays.sort(qidxs, (j, i) -> queries[i][0] - queries[j][0]);

        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        Set<Integer> set = new HashSet<>();
        for (int x : nums2) set.add(x);
        for (int[] q : queries) set.add(q[1]);
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        int sz = list.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sz; i++) map.put(list.get(i), i);

        // 用树状数组维护nums2的后缀最大值
        FenwickTree tr = new FenwickTree(sz + 10);  
        int j = 0;  // 从j=0开始遍历nums1和nums2
        for (int qidx : qidxs) {  // // 对于每个query，维护树状数组，通过树状数组得到每个query的最大值
            int x = queries[qidx][0], y = queries[qidx][1];
            for (; j < n && nums1[idxs[j]] >= x; j++) {
                int idx = idxs[j];
                tr.add(sz - map.get(nums2[idx]), nums1[idx] + nums2[idx]);  // 通过'sz - '倒排树状数组，实现求后缀最大值的目的
            }
            res[qidx] = tr.query(sz - map.get(y));
        }
        return res;
    }
}