数组范围内计数

数组为 3,2,2,3,1, 查询为（0,3,2)。

意思是在数组里下标 0-3 这个范围上，有几个 2?

假设给一个数组 arr，对这个数组的查询非常频繁请返回所有查询的结果。

给出：arr[ ]

要查多个范围：

[[0,3,2],

[1,4,0]]

结果返回：[第一个数组结果，第二个数组结果]

暴力解法直接遍历肯定不可以。

解法

一、做一个map映射，遍历一遍数组，将每个值和每个值出现的下标位置数组做成key-value

在根据查询的V，在所在值的数组内做二分查找。

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
public static class QueryBox2 {
        private HashMap<Integer, ArrayList<Integer>> map;

        public QueryBox2(int[] arr) {
            map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                if (!map.containsKey(arr[i])) {
                    map.put(arr[i], new ArrayList<>());
                }
                map.get(arr[i]).add(i);
            }
        }

        public int query(int L, int R, int value) {
            if (!map.containsKey(value)) return 0;
            ArrayList<Integer> indexArr = map.get(value);
            // 查询<L的下标有几个
            int a = countLess(indexArr, L);
            // 查询<R+1的下标有几个
            int b = countLess(indexArr, R + 1);
            return b - a;
        }

        // 在有序数组中，用二分法数出<limit 的数有几个
        // 也就是用二分法，找到<limit的数中最右的位置
        private int countLess(ArrayList<Integer> arr, int limit) {
            int L = 0;
            int R = arr.size() - 1;
            int mostRight = -1;
            while (L <= R) {
                int mid = L + ((R - L) >> 1);
                if (arr.get(mid) < limit) {
                    mostRight = mid;
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            return mostRight + 1;
        }
    }

$O(mlogn)$

扩展：

如果是求范围内累加和

可以生成一个前缀和数组类似本题

腾讯原题

给定整数 power。给定一个数组 arr。给定一个数组 reverse。含义如下

arr 的长度一定是 2 的 power 次方，reverse1 每个值一定都在 0 ~ power范围。

例如 power=2, ar={3,1,4,2}, reverse={0,1,0,2}

针对reverse的数组中每一个值

如第一个值为0，就是对$2^0=1$ 每一个arr数组以1个数为单位逆序。

如第二个值为1，就是对$2^1=2$ 对arr数组每两个数逆序

任何一个在前的数字可以和任何一个在后的数组，构成一对数。可能是升序关系、相等关系或者降序关系。

最后求调整完的arr数组有多少个降序对。

比如 arr 开始时有如下的降序对：(3,1)、（3.2)、（4.2），一共 3 个。

以2个数调整后arr由{3,1,4,2} 变成{1,3,2,4} 降序对有{3,2} ，共1个

经典做法每次都reverse

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
// originArr长度一定是2的power次方
    // reverseArr中每一个值，都是0-power范围上的数
    public static int[] reversePair1(int[] originArr, int[] reverseArr, int power) {
        int[] ans = new int[reverseArr.length];
        for (int i = 0; i < reverseArr.length; i++) {
            // 1 << (reverseArr[i]) == r[i]的2次方
            reverseArray(originArr, 1 << (reverseArr[i]));
            ans[i] = countReversePair(originArr);
        }
        return ans;
    }

    public static void reverseArray(int[] originArr, int teamSize) {
        if (teamSize < 2) return;
        for (int i = 0; i < originArr.length; i += teamSize) {
            reversePart(originArr, i, i + teamSize - 1);
        }
    }

    public static void reversePart(int[] arr, int L, int R) {
        while (L < R) {
            int temp = arr[L];
            arr[L++] = arr[R];
            arr[R--] = temp;
        }
    }

    public static int countReversePair(int[] originArr) {
        int ans = 0;
        for (int i = 0; i < originArr.length; i++) {
            for (int j = i + 1; j < originArr.length; j++) {
                if (originArr[i] > originArr[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }

优化方案

[3,2 4,5, 0,1 3,5]

两个数一组： 1个逆序对，3个升序对

四个数一组： 0个逆序对，8个升序对

八个数一组：10个逆序对，4个升序对

每个数组的逆序对数是2、4、9个一组的加和

当数组进行几个数一组翻转时

翻转后的逆序对和升序对数量，和翻转前的升序对和逆序对相等，数量调换了。

小的数调整后数量不影响大数量调整后的数量。

所以直接查2、4、8、16个 数量再交换相加。

如何高效生成预处理记录

输入数据状况

power范围[0,20]

arr长度范围[1,10e7]

reverse长度范围[1,10e6]

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
public static int[] reversePair2(int[] originArr, int[] reverseArr, int power) {
        int[] originReverse = Arrays.copyOf(originArr, originArr.length);
        reversePart(originReverse, 0, originReverse.length - 1);
        int[] recordDown = new int[power + 1];
        int[] recordUp = new int[power + 1];
        process(originArr, 0, originArr.length - 1, power, recordDown);
        process(originReverse, 0, originReverse.length - 1, power, recordUp);

        // recordDown[i] 2的i次方个数一组的划分中，降序的数量
        // recordUp[i] 2的i次方个数一组的划分中，升序的数量
        int[] ans = new int[reverseArr.length];
        for (int i = 0; i < reverseArr.length; i++) {
            int curPower = reverseArr[i]; // =3  2的1次方、2次方、3次方 要调整
            for (int p = 1; p <= curPower; p++) {
                int tmp = recordDown[p];
                recordDown[p] = recordUp[p];
                recordUp[p] = tmp;
            }
            for (int p = 1; p <= power; p++) {
                ans[i] += recordDown[p];
            }
        }
        return ans;
    }

    public static void process(int[] originArr, int L, int R, int power, int[] record) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(originArr, L, mid, power - 1, record);
        process(originArr, mid + 1, R, power - 1, record);
        record[power] += merge(originArr, L, mid, R);
    }

    public static int merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = m + 1;
        int ans = 0;
        while (p1 <= m && p2 <= r) {
            ans += arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return ans;
    }