2023年7月26日每日一题--2569. 更新数组后处理求和查询

难度 极大

leetcode链接：

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

题目分析

尝试暴力求解

见识短浅，感觉题目都没看明白，然后尝试使用暴力求解， 77个中72个通过了测试，感觉题目应该看对了，要不然还不会有72个通过。但是如果看对了，为什么倒数第5个找不到呐，实在不明白，甚是烦恼。看官方题解也是一知半解

方案一

class Solution {
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        List<Long> result = new ArrayList<>();

        for (int i = 0; i < queries.length; i++) {

            if (queries[i][0] == 1) {

                for (int j = queries[i][1]; j <= queries[i][2]; j++) {
                    if (nums1[j] == 0){
                        nums1[j] = 1;
                    } else {
                        nums1[j] = 0;
                    }
                }
            } else if (queries[i][0] == 2) {
                for (int j = 0; j < nums2.length; j++) {
                    nums2[j] = (int) ((long) nums2[j] + nums1[j] * queries[i][1]);
                }
            } else {
                long tem = 0L;
                for (int j = 0; j < nums2.length; j++) {
                    tem += nums2[j];
                }
                result.add(tem);
            }
        }

        long[] longRes = new long[result.size()];

        for (int i = 0; i < result.size(); i++) {
            longRes[i] = result.get(i);
        }

        return longRes;
    }
}

结果

解答错误
72 / 77 个通过测试用例

分析

时间复杂度：
O( max( n, m ) * p )

空间复杂度：
O( p )

官方题解

其使用了线段数的相关思想。目前还未学到相关知识。

线段树相关内容介绍：

https://oi-wiki.org/ds/seg/
https://zhuanlan.zhihu.com/p/629713516

官方相关题解：

https://leetcode.cn/problems/handling-sum-queries-after-update/solution/geng-xin-shu-zu-hou-chu-li-qiu-he-cha-xu-kv6u/
https://leetcode.cn/problems/handling-sum-queries-after-update/solution/python3javacgo-yi-ti-yi-jie-xian-duan-sh-maq2/

class Solution {
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        int m = queries.length;
        SegTree tree = new SegTree(nums1);
        
        long sum = 0;
        for (int num : nums2) {
            sum += num;
        }
        List<Long> list = new ArrayList<Long>();
        for (int i = 0; i < m; i++) {
            if (queries[i][0] == 1) {
                int l = queries[i][1];
                int r = queries[i][2];
                tree.reverseRange(l, r);
            } else if (queries[i][0] == 2) {
                sum += (long) tree.sumRange(0, n - 1) * queries[i][1];
            } else if (queries[i][0] == 3) {
                list.add(sum);
            }
        }
        long[] ans = new long[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

class SegTree {
    private SegNode[] arr;

    public SegTree(int[] nums) {
        int n = nums.length;
        arr = new SegNode[n * 4 + 1];
        build(1, 0, n - 1, nums);
    }

    public int sumRange(int left, int right) {
        return query(1, left, right);
    }

    public void reverseRange(int left, int right) {
        modify(1, left, right);
    }

    public void build(int id, int l, int r, int[] nums) {
        arr[id] = new SegNode();
        arr[id].l = l;
        arr[id].r = r;
        arr[id].lazytag = false;
        if(l == r) {
            arr[id].sum = nums[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * id, l, mid, nums);
        build(2 * id + 1, mid + 1, r, nums);
        arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum;
    }

    /* pushdown函数：下传懒标记，即将当前区间的修改情况下传到其左右孩子结点 */
    public void pushdown(int x) {
        if(arr[x].lazytag) {
            arr[2 * x].lazytag = !arr[2 * x].lazytag;
            arr[2 * x].sum = arr[2 * x].r - arr[2 * x].l + 1 - arr[2 * x].sum;
            arr[2 * x + 1].lazytag = !arr[2 * x + 1].lazytag;
            arr[2 * x + 1].sum = arr[2 * x + 1].r - arr[2 * x + 1].l + 1 - arr[2 * x + 1].sum;
            arr[x].lazytag = false;
        }
    }

    /* 区间修改 */
    public void modify(int id, int l, int r) {
        if (arr[id].l >= l && arr[id].r <= r) {
            arr[id].sum = (arr[id].r - arr[id].l + 1) - arr[id].sum;
            arr[id].lazytag = !arr[id].lazytag;
            return;
        }
        pushdown(id);
        int mid = (arr[id].l + arr[id].r) >> 1;
        if (arr[2 * id].r >= l) {
            modify(2 * id, l, r);
        }
        if(arr[2 * id + 1].l <= r) {
            modify(2 * id + 1, l, r);
        }
        arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum;
    }
    
    /* 区间查询 */
    public int query(int id, int l, int r) {
        if (arr[id].l >= l && arr[id].r <= r) {
            return arr[id].sum;
        }
        if (arr[id].r < l || arr[id].l > r) {
            return 0;
        }
        pushdown(id);
        int res = 0;
        if (arr[2 * id].r >= l) {
            res += query(2 * id, l, r);
        }
        if (arr[2 * id + 1].l <= r) {
            res += query(2 * id + 1, l, r);
        }
        return res;
    }
}

class SegNode {
    public int l, r, sum;
    public boolean lazytag;

    public SegNode() {
        this.l = 0;
        this.r = 0;
        this.sum = 0;
        this.lazytag = false;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/handling-sum-queries-after-update/solution/geng-xin-shu-zu-hou-chu-li-qiu-he-cha-xu-kv6u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。