2569. 更新数组后处理求和查询

给你两个下标从 0 开始的数组 nums1 和 nums2 ，和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作：

  1. 操作类型 1 为 queries[i] = [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 并且所有 1 反转成 0 。l 和 r 下标都从 0 开始。
  2. 操作类型 2 为 queries[i] = [2, p, 0] 。对于 0 <= i < n 中的所有下标，令 nums2[i] = nums2[i] + nums1[i] * p 。
  3. 操作类型 3 为 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。

请你返回一个 数组，包含 所有第三种操作类型 的答案。

示例 1：

1
2
3
输入：nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
输出：[3]
解释：第一个操作后 nums1 变为 [1,1,1] 。第二个操作后，nums2 变成 [1,1,1] ，所以第三个操作的答案为 3 。所以返回 [3] 。

示例 2：

1
2
3
输入：nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
输出：[5]
解释：第一个操作后，nums2 保持不变为 [5] ，所以第二个操作的答案是 5 。所以返回 [5] 。

提示：

  • 1 <= nums1.length,nums2.length <= 10^5
  • nums1.length = nums2.length
  • 1 <= queries.length <= 10^5
  • queries[i].length = 3
  • 0 <= l <= r <= nums1.length - 1
  • 0 <= p <= 10^6
  • 0 <= nums1[i] <= 1
  • 0 <= nums2[i] <= 10^9

指针lazy线段树，区间覆盖更新，存储区间和

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
class Solution {
    class Node {
        Node l, r;
        int len;
        long val, lazy;
    }
    Node root = new Node();
    void pushDown(Node cur, int l, int r) {
        int m = l + (r-l)/2;
        if (cur.l == null) {
            cur.l = new Node();
            cur.l.len = m - l + 1;
        }
        if (cur.r == null) {
            cur.r = new Node();
            cur.r.len = r - m;
        }
        if (cur.lazy == 1) {
            cur.l.lazy = 1 - cur.l.lazy;
            cur.r.lazy = 1 - cur.r.lazy;
            cur.l.val = cur.l.len - cur.l.val;
            cur.r.val = cur.r.len - cur.r.val;
            cur.lazy = 1 - cur.lazy;
        }
    }
    void pushUp(Node cur) {
        cur.val = cur.l.val + cur.r.val;
    }
    void upd(Node cur, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            cur.val = r - l + 1 - cur.val;
            cur.lazy = 1 - cur.lazy;
        }
        else {
            pushDown(cur, l, r);
            int m = l + (r-l)/2;
            if (tl <= m) upd(cur.l, l, m, tl, tr);
            if (m+1 <= tr) upd(cur.r, m+1, r, tl, tr);
            pushUp(cur);
        }
    }
    long query(Node cur, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            return cur.val;
        }
        else {
            pushDown(cur, l, r);
            int m = l + (r-l)/2, res = 0;
            if (tl <= m) res += query(cur.l, l, m, tl, tr);
            if (m+1 <= tr) res += query(cur.r, m+1, r, tl, tr);
            pushUp(cur);
            return res;
        }
    }
    void build(Node cur, int l, int r, int[] nums) {
        if (l == r) {
            cur.val = nums[l];
        }
        else {
            pushDown(cur, l, r);
            int m = l + (r - l) / 2;
            build(cur.l, l, m, nums);
            build(cur.r, m + 1, r, nums);
            pushUp(cur);
        }
    }
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        List<Long> list = new ArrayList<>();
        int n = nums1.length;
        build(root, 0, n-1, nums1);
        long sum = 0;
        for (int num : nums2) sum += num;
        for (int[] q : queries) {
            if (q[0] == 1) {
                upd(root, 0, n-1, q[1], q[2]);
            }
            else if (q[0] == 2) {
                sum += q[1] * query(root, 0, n-1, 0, n-1);
            }
            else {
                list.add(sum);
            }
        }
        long[] res = new long[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        return res;
    }
}

数组lazy线段树，区间覆盖更新，存储区间和

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
class Solution {
    int[] nums;
    int len;
    long[] tree;
    int[] lazy;
    void pushDown(int idx, int l, int r) {
        if (lazy[idx] != 0) {
            int m = l + (r-l)/2;
            tree[2 * idx] = m - l + 1 - tree[2 * idx];
            tree[2 * idx + 1] = r - m - tree[2 * idx + 1];
            lazy[2 * idx] = 1 - lazy[2 * idx];
            lazy[2 * idx + 1] = 1 - lazy[2 * idx + 1];
            lazy[idx] = 1 - lazy[idx];
        }
    }
    void pushUp(int idx) {
        tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
    }
    void upd(int idx, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            tree[idx] = r - l + 1 - tree[idx];
            lazy[idx] = 1 - lazy[idx];
        } else {
            pushDown(idx, l, r);
            int m = l + (r - l) / 2;
            if (tl <= m) upd(2 * idx, l, m, tl, tr);
            if (m + 1 <= tr) upd(2 * idx + 1, m + 1, r, tl, tr);
            pushUp(idx);
        }
    }
    long query(int idx, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            return tree[idx];
        } else {
            pushDown(idx, l, r);
            int m = l + (r - l) / 2;
            int res = 0;
            if (tl <= m) res += query(2 * idx, l, m, tl, tr);
            if (m + 1 <= tr) res += query(2 * idx + 1, m + 1, r, tl, tr);
            return res;
        }
    }
    void build(int idx, int l, int r) {
        if (l == r) {
            tree[idx] = nums[l];
        } else {
            int m = l + (r - l) / 2;
            build(2 * idx, l, m);
            build(2 * idx + 1, m + 1, r);
            pushUp(idx);
        }
    }
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        this.nums = nums1;
        this.len = nums1.length;
        tree = new long[4 * len];
        lazy = new int[4 * len];
        build(1, 0, len - 1);
        List<Long> list = new ArrayList<>();
        int n = nums1.length;
        long sum = 0;
        for (int num : nums2) sum += num;
        for (int[] q : queries) {
            if (q[0] == 1) {
                upd(1, 0, n-1, q[1], q[2]);
            }
            else if (q[0] == 2) {
                sum += q[1] * query(1, 0, n-1, 0, n-1);
            }
            else {
                list.add(sum);
            }
        }
        long[] res = new long[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        return res;
    }
}