https://leetcode.cn/problems/minimum-operations-to-make-array-elements-zero/solutions/3774178/da-biao-fa-by-dzcgi6z0qk-pcda

打表法：table里面存入1~1e9中4的倍数。求[r,l]之间需要操作的次数等价于求[1,r]减去[1,l-1]操作的次数。

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
class Solution {
    public long minOperations(int[][] queries) {
        long[] table = {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824};
        int n = queries.length;
        long ans = 0;
        for (int i = 0; i < n; i ++) {
            long l = queries[i][0] - 1;
            long r = queries[i][1];
            long cnt = 0;
            for (int j = 0; j < table.length; j ++) {
                if (r >= table[j] && r < 4 * table[j]) {
                    cnt += (j + 1) * (r - table[j] + 1);
                    break;
                } else {
                    cnt += (j + 1) * 3 * table[j];
                }
            }
            if (l == 0) {
                ans += cnt % 2 == 0 ? cnt / 2 : cnt / 2 + 1;
                continue;
            }
            for (int j = 0; j < table.length; j ++) {
                if (l >= table[j] && l < 4 * table[j]) {
                    cnt -= (j + 1) * (l - table[j] + 1);
                    break;
                } else {
                    cnt -= (j + 1) * 3 * table[j];
                }
            }
            ans += cnt % 2 == 0 ? cnt / 2 : cnt / 2 + 1;
        }
        return ans;
    }
}