医院网站云服务器配置,免费自助站制作在线,四川住房和城乡建设厅官方网站,建站超市本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你两个下标从 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^5nums1.length nums2.length1 queries.length 10^5queries[i].length 30 l r nums1.length - 10 p 10^60 nums1[i] 10 nums2[i] 10^9 解法 线段树区间更新和区间查询
线段树是一个二叉树每个结点保存数组 n u m s nums nums 在区间 [ s , e ] [s,e] [s,e] 的最小值、最大值或者总和等信息。线段树可以用树也可以用数组堆式存储来实现。对于数组实现假设根结点的下标为 1 1 1 如果一个结点在数组的下标为 n o d e node node 那么它的左子结点下标为 n o d e × 2 node\times 2 node×2 右子结点下标为 node × 2 1 \textit{node} \times 2 1 node×21 线段树可以在 O ( log N ) O(\log N) O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询区间求和求区间最大值求区间最小值等操作关于线段树的详细描述可以参考「线段树」。
区间更新的线段树需要借助「懒惰标记」来标记当前结点所在区间是否需要更新。
建树 b u i l d build build 函数
我们在结点 n o d e node node 保存数组 nums \textit{nums} nums 在区间 [ s , e ] [s,e] [s,e] 的总和。 s e s e se 时结点 n o d e node node 是叶子结点它保存的值等于 n u m s [ s ] nums[s] nums[s] 。 s e se se 时结点 n o d e node node 的左子结点保存区间 [ s , ⌊ s e 2 ⌋ ] \Big [ s, \Big \lfloor \dfrac{s e}{2} \Big \rfloor \Big ] [s,⌊2se⌋] 的总和右子结点保存区间 [ ⌊ s e 2 ⌋ 1 , e ] \Big [ \Big \lfloor \dfrac{s e}{2} \Big \rfloor 1, e \Big ] [⌊2se⌋1,e] 的总和那么结点 n o d e node node 保存的值等于它的两个子结点保存的值之和。
假设 n u m s nums nums 的大小为 n n n 我们规定根结点 n o d e 1 node1 node1 保存区间 [ 0 , n − 1 ] [0, n - 1] [0,n−1] 的总和然后自下而上递归地建树。
区间修改 m o d i f y modify modify 函数当要修改区间 n u m s [ l e f t ⋯ r i g h t ] nums[left⋯right] nums[left⋯right] 的值时查看当前区间的结点此前是否已经「更新」过。如果更新过那么通过 p u s h d o w n pushdown pushdown 函数将更新标记传递到子结点对之前的操作进行更新同时更新设置每个结点的懒标记 l a z y t a g lazytag lazytag 后续该位置便可以认为无需进行更新操作。区间查询 q u e r y query query 函数给定区间 [ l e f t , r i g h t ] [left, right] [left,right] 时也需要像区间更新操作一样需要使用 p u s h d o w n pushdown pushdown 函数将更新标记往下传递到子结点否则区间本身的数值实际上没有更新懒标记只在区间修改或者区间查询时会往下传递否则只是标记该区间需要更新。将区间 [ l e f t , r i g h t ] [left, right] [left,right] 拆成多个结点对应的区间。 如果结点 n o d e node node 对应的区间与 [ l e f t , r i g h t ] [left, right] [left,right] 相同可以直接返回该结点的值即当前区间和。如果结点 n o d e node node 对应的区间与 [ l e f t , r i g h t ] [left, right] [left,right] 不同设左子结点对应的区间的右端点为 m m m 那么将区间 [ l e f t , r i g h t ] [left, right] [left,right] 沿点 m m m 拆成两个区间分别向下传递懒标记并计算左子结点和右子结点。从根结点开始递归地拆分区间 [ l e f t , r i g h t ] [left, right] [left,right]边拆分边计算并返回最终结果即可。
本题目中含有三种操作
第一种操作是将给定区间 [ l e f t , r i g h t ] [left, right] [left,right] 内的所有数据进行反转实际为是区间更新此时我们可以利用线段树进行区间更新此时需要用到「线段树的区间修改与懒惰标记」。第二种操作是唯一对 n u m s 2 nums_2 nums2 中的元素进行更新此时 nums 2 ′ [ i ] nums 2 [ i ] nums 1 [ i ] × p \textit{nums}_2[i] \textit{nums}_2[i] \textit{nums}_1[i] \times p nums2′[i]nums2[i]nums1[i]×p 设数组 nums 2 \textit{nums}_2 nums2 更新之前的和为 s u m sum sum 更新之后的和为 s u m ′ sum′ sum′ 。再假设 n u m s 1 nums_1 nums1 中总共有 c c c 个 1 1 1 那么操作2相当于把 n u m s 2 nums_2 nums2 的元素和增加了 c × p c \times p c×p 。计算过程如下 sum ′ ∑ i 0 n − 1 nums 2 ′ [ i ] ∑ i 0 n − 1 ( nums 2 [ i ] nums 1 [ i ] × p ) ∑ i 0 n − 1 nums 2 [ i ] p × ∑ i 0 n − 1 nums 1 [ i ] sum p × ∑ i 0 n − 1 nums 1 [ i ] \begin{aligned} \textit{sum} \sum\limits_{i0}^{n-1}{\textit{nums}_2[i]} \\ \sum\limits_{i0}^{n-1}(\textit{nums}_2[i] \textit{nums}_1[i] \times p) \\ \sum\limits_{i0}^{n-1}\textit{nums}_2[i] p \times \sum\limits_{i0}^{n-1}\textit{nums}_1[i] \\ \textit{sum} p \times \sum\limits_{i0}^{n-1}\textit{nums}_1[i] \end{aligned} sum′i0∑n−1nums2′[i]i0∑n−1(nums2[i]nums1[i]×p)i0∑n−1nums2[i]p×i0∑n−1nums1[i]sump×i0∑n−1nums1[i] 根据上述等式可以看到每次执行操作二时实际 n u m 2 num_2 num2 的和会加上 p p p 倍 n u m 1 num_1 num1 的元素之和可在每次更新时维护数组 n u m 2 num_2 num2 的和。由于 n u m 1 num_1 num1 初始化时全部为 0 0 0 经过第一种操作时部分元素会进行反转因此只需要用线段树维护区间内 1 1 1 的个数每次进行区间查询即可得到数组 n u m 1 num_1 num1 的元素之和。第三种操作是求数组 n u m 2 num_2 num2 的元素之和此时返回操作二中维护的 n u m 2 num_2 num2 的和即可。
根据以上分析建立区间更新的线段树可以参考「线段树的区间修改与懒惰标记」当遇到操作一时进行区间更新遇到操作二时进行区间查询即可。
struct SegNode {int l, r, sum;bool lazyTag;SegNode() {l r sum 0;lazyTag false;}
};
class SegTree {
private:vectorSegNode arr;
public:SegTree(vectorint nums) {int n nums.size();arr vectorSegNode(n * 4 1);build(1, 0, n - 1, nums);}void build(int id, int l, int r, const vectorint nums) {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函数下传懒标记将当前区间的修改情况下放到其左右孩子结点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; // 翻转后1的个数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;}}/** 区间修改 **/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;}/** 区间查询 **/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 ans 0;if (arr[2 * id].r l) ans query(2 * id, l, r);if (arr[2 * id 1].l r) ans query(2 * id 1, l, r);return ans;}int sumRange(int left, int right) {return query(1, left, right);}void reverseRange(int left, int right) {modify(1, left, right);}
};
class Solution {
public:vectorlong long handleQuery(vectorint nums1, vectorint nums2, vectorvectorint queries) {int n nums1.size();int m queries.size();SegTree tree(nums1);long long sum accumulate(nums2.begin(), nums2.end(), 0LL);vectorlong long ans;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 long) tree.sumRange(0, n - 1) * queries[i][1];} else if (queries[i][0] 3) {ans.emplace_back(sum);}}return ans;}
};复杂度分析
时间复杂度 O ( m log n ) O(m \log n) O(mlogn) 其中 m m m 表示操作 1 1 1 与操作 2 2 2 的次数之和 n n n 表示数组的长度。每次遇到操作类型 1 1 1 与操作类型 2 2 2 时需要更新线段树线段树每次更新与查询的时间复杂度均为 O ( log n ) O(\log n) O(logn) 一共最多有 m m m 次操作因此总的时间复杂度为 O ( m log n ) O(m \log n) O(mlogn) 。空间复杂度 O ( C n ) O(Cn) O(Cn) 其中 n n n 表示数组的长度。本题解中线段树采用堆式存储假设当前数组的长度为 n n n 由于线段树是一棵完全二叉树此时该树的最大深度为 ⌈ log n ⌉ \lceil \log n \rceil ⌈logn⌉ 则其叶子结点的总数为 2 ⌈ log n ⌉ 2^{\lceil \log n \rceil} 2⌈logn⌉ 该树中含有的结点总数为 2 ⌈ log n ⌉ 1 − 1 2^{\lceil \log n \rceil 1} - 1 2⌈logn⌉1−1 此时可以知道 2 ⌈ log n ⌉ 1 − 1 ≤ 2 log n 2 − 1 ≤ 4 n − 1 2^{\lceil \log n \rceil 1} - 1 \le 2^{\log n 2} - 1 \le 4n - 1 2⌈logn⌉1−1≤2logn2−1≤4n−1 因此本题中取 C 4 C4 C4 即可。
