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

题目描述

给你两个下标从 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 <= 105
nums1.length = nums2.length
1 <= queries.length <= 105
queries[i].length = 3
0 <= l <= r <= nums1.length - 1
0 <= p <= 106
0 <= nums1[i] <= 1
0 <= nums2[i] <= 109

解题思路

思路1：最直观的想法是，暴力模拟。（很显然超时）

class Solution {
public:vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {vector<long long> res;for(auto query:queries){int a=query[0];int b=query[1];int c=query[2];switch(a){case 1:for(int i=b;i<=c;i++)nums1[i]=!nums1[i];break;case 2:for(int i=0;i<nums2.size();i++)nums2[i]+=nums1[i]*b;break;case 3:long long sum=accumulate(nums2.begin(),nums2.end(),0.0);res.push_back(sum);          }}return res;}};

思路2：涉及到区间修改以及区间查询，一般使用线段树。线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。线段树每个节点有一个编号i，其表示区间[l,r]的元素和，该元素左节点有一个编号2*i，其表示区间[l,m]的元素和，该元素右节点有一个编号2*i+1，其表示区间[m+1,r]的元素和，其中m=l+(r-l)/2。其中我们可以给每个节点加上标记tag，当修改时修改当前tag和区间和，等到下次查询时再将tag下放。

class Solution {
public://节点个数 最多4nstatic constexpr int MX=4e5+1;//区间1的个数int cnt1[MX];//整个区间是否需要翻转标记bool flip[MX];//维护区间1的个数void maintain(int o){//当前节点对应区间的1的数量等于左右孩子对应区间1的个数cnt1[o]=cnt1[2*o]+cnt1[2*o+1];}//执行区间翻转 o为当前节点下标 [l,r]为区间void do_(int o,int l,int r){//区间长度减去原本1的个数即原本0的个数即翻转后1的个数cnt1[o]=r-l+1-cnt1[o];flip[o]=!flip[o];}//初始化线段树 o是节点标记 从1开始 但是数组下标从0开始void build(vector<int>&a,int o,int l,int r){//只有一个元素直接求和if(l==r){cnt1[o]=a[l-1];return;}//分成区间求和int m=l+(r-l)/2;//左孩子标记为o*2 左区间为[l,m]build(a,o*2,l,m);//右孩子标记为o*2+1 右区间为[m+1,r]build(a,o*2+1,m+1,r);//该节点区间和为左右孩子区间和之和maintain(o);}//翻转区间 当前标记为o 当前区间为[l,r] 当前待更新区间为[L,R]  void update(int o,int l,int r,int L,int R){//[L,R]在[l,r]内部if(L<=l&&r<=R){do_(o,l,r);return;}//分而治之int m=l+(r-l)/2;//如果有标记则需要向下传递标记并且清空当前节点之前的标记情况if(flip[o]){do_(o*2,l,m);do_(o*2+1,m+1,r);flip[o]=false;}//左区间有交集if(m>=L)update(o*2,l,m,L,R);//右区间有交集if(m<R)update(o*2+1,m+1,r,L,R);//该节点区间和为左右孩子区间和之和maintain(o);}vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {int n=nums1.size();build(nums1,1,1,n);vector<long long> res;long long sum=accumulate(nums2.begin(),nums2.end(),0LL);for(auto q:queries){if(q[0]==1)update(1,1,n,q[1]+1,q[2]+1);else if(q[0]==2)sum+=1LL*q[1]*cnt1[1];elseres.push_back(sum);}return res;}
};

总结：https://oi-wiki.org/ds/seg/讲得很好！！