基于LeetCode每日一题的Java编程语言设计源码分享

//package com.anna.leetcode; // //import java.util.ArrayList; //import java.util.Arrays; //import java.util.LinkedList; //import java.util.List; // //// 2569. Handling Sum Queries After Update //// 更新数组后处理求和查询 //// https://leetcode.cn/problems/handling-sum-queries-after-update/ //public class HandlingSumQueriesAfterUpdate { // // /* // 给你两个下标从 0 开始的数组 nums1 和 nums2 ，和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作： // 操作类型 1 为 queries[i] = [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。 // 操作类型 2 为 queries[i] = [2, p, 0] 。对于 0 <= i < n 中的所有下标，令 nums2[i] = nums2[i] + nums1[i] * p 。 // 操作类型 3 为 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。 // 请你返回一个数组，包含所有第三种操作类型的答案。 // 示例 1： // 输入：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： // 输入：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 // */ // // public static void main(String[] args) { // int[] nums1 = {0,1,0,0,0,0}; // int[] nums2 = {14,4,13,13,47,18}; // int[][] queries = {{3,0,0},{1,4,4},{1,1,4},{1,3,4},{3,0,0},{2,5,0},{1,1,3},{2,16,0},{2,10,0},{3,0,0} // ,{3,0,0},{2,6,0}}; // Solution1 so1 = new Solution1(); // System.out.println(Arrays.toString(so1.handleQuery(cp(nums1), cp(nums2), cp(queries)))); // Solution2 so2 = new Solution2(); // System.out.println(Arrays.toString(so2.handleQuery(cp(nums1), cp(nums2), cp(queries)))); // Solution3 so3 = new Solution3(); // System.out.println(Arrays.toString(so3.handleQuery(cp(nums1), cp(nums2), cp(queries)))); // } // // public static int[] cp(int[] arr) { // int[] res = new int[arr.length]; // System.arraycopy(arr, 0, res, 0, arr.length); // return res; // } // // public static int[][] cp(int[][] arr) { // int[][] res = new int[arr.length][]; // for (int i = 0; i < arr.length; i++) { // res[i] = cp(arr[i]); // } // return res; // } // // // // indexTree 暴力 // private static class Solution1 { // public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) { // int N = nums1.length; // IndexTree it = new IndexTree(N); // for (int i = 0; i < N; i++) { // it.add(i + 1, nums2[i]); // } // List<Long> ans = new ArrayList<>(); // for (int[] q : queries) { // switch (q[0]) { // case 1 -> { // for (int i = q[1]; i <= q[2]; i++) { // nums1[i] = nums1[i] ^ 1; // } // } // case 2 -> { // for (int i = 0; i < N; i++) { // it.add(i + 1, q[1] * nums1[i]); // } // } // case 3 -> ans.add(it.sum(N)); // default -> throw new IllegalArgumentException("IllegalArgument queries!"); // } // } // return ans.stream().mapToLong(Long::longValue).toArray(); // } // // // indexTree // private static class IndexTree { // long[] arr; // int MAXN; // // public IndexTree(int size) { // this.MAXN = size + 1; // this.arr = new long[MAXN]; // } // // // // 从一开始 // public void add(int index, int val) { // while (index < MAXN) { // arr[index] += val; // index += index & (-index); // } // } // // // // index下标从1开始 // // sum[1 - index] // public long sum(int index) { // long sum = 0; // while (index > 0) { // sum += arr[index]; // index -= index & (-index); // } // return sum; // } // } // } // // // // 优化(失败)： // // 考虑到nums1只有0 1, 且第二部变动为nums[2] + q * nums1[i] ==> nums[2] + (0\q) // // 设nums2的和为sum2, nums1中一的个数为oneNum, 零的个数zeroNum // // 第三步求和转换为sum2 + oneNum * q // // ▲：如何维护sum2, 变动的维护oneNum -> [1, l, r] nums1 中l->r 0转换为1，1转换为0 -> 随时能区间查询1\0的个数 // private static class Solution2 { // // public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) { // int N = nums1.length; // // 记录nums1中1的个数 // SegmentTree st = new SegmentTree(N); // for (int i = 0; i < N; i++) { // if (nums1[i] == 1) { // st.add(i + 1, i + 1, nums1[i]); // } // } // long sum2 = 0; // for (int num : nums2) sum2 += num; // List<Long> ans = new LinkedList<>(); // for (int[] q : queries) { // switch (q[0]) { // case 1 -> { // int l = q[1] + 1, r = q[2] + 1; // // 更新一的个数 总个数 - 原有一的个数 （反转） // // 此处待优化点：★★★★★★ // // 如何灵活使用线段树，维护1与0的位置信息 不是生硬的add, update // for (int i = l; i <= r; i++) { // nums1[i - 1] ^= 1; // st.update(i, i, nums1[i - 1]); // } // } // case 2 -> { // // nums2[i] = nums2[i] + nums1[i] * p; nums[1] = 0 / 1 // // 推出 sum2 = sum2 + (p * oneNum) // sum2 += (long) st.query(1, N) * q[1]; // } // case 3 -> { // ans.add(sum2); // } // default -> throw new IllegalArgumentException("IllegalArgument queries"); // } // } // return ans.stream().mapToLong(Long::longValue).toArray(); // } // // // private static class SegmentTree { // // Node root; // // [1~size] // int size; // // public SegmentTree(int size) { // this.size = size; // this.root = new Node(); // } // // public void add(int L, int R, int C) { // add(L, R, C, 1, size, root); // } // // public void update(int L, int R, int C) { // update(L, R, C, 1, size, root); // } // // public int query(int L, int R) { // return query(L, R, 1, size, root); // } // // void add(int L, int R, int C, int l, int r, Node cur) { // if (L <= l && r <= R) { // cur.lazy += C; // cur.val += C * (r - l + 1); // return; //