义乌企业网站建设,丰富网站内容,百度一下网页版浏览器百度,wordpress 3.6【每日一题】2569. 更新数组后处理求和查询 2569. 更新数组后处理求和查询题目描述解题思路 2569. 更新数组后处理求和查询
题目描述
给你两个下标从 0 开始的数组 nums1 和 nums2 #xff0c;和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作#xff1a;
操作… 【每日一题】2569. 更新数组后处理求和查询 2569. 更新数组后处理求和查询题目描述解题思路 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:vectorlong long handleQuery(vectorint nums1, vectorint nums2, vectorvectorint queries) {vectorlong long res;for(auto query:queries){int aquery[0];int bquery[1];int cquery[2];switch(a){case 1:for(int ib;ic;i)nums1[i]!nums1[i];break;case 2:for(int i0;inums2.size();i)nums2[i]nums1[i]*b;break;case 3:long long sumaccumulate(nums2.begin(),nums2.end(),0.0);res.push_back(sum); }}return res;}};思路2涉及到区间修改以及区间查询一般使用线段树。线段树将每个长度不为 1 的区间划分成左右两个区间递归求解把整个线段划分为一个树形结构通过合并左右两区间信息来求得该区间的信息。线段树每个节点有一个编号i其表示区间[l,r]的元素和该元素左节点有一个编号2*i其表示区间[l,m]的元素和该元素右节点有一个编号2*i1其表示区间[m1,r]的元素和其中ml(r-l)/2。其中我们可以给每个节点加上标记tag当修改时修改当前tag和区间和等到下次查询时再将tag下放。
class Solution {
public://节点个数 最多4nstatic constexpr int MX4e51;//区间1的个数int cnt1[MX];//整个区间是否需要翻转标记bool flip[MX];//维护区间1的个数void maintain(int o){//当前节点对应区间的1的数量等于左右孩子对应区间1的个数cnt1[o]cnt1[2*o]cnt1[2*o1];}//执行区间翻转 o为当前节点下标 [l,r]为区间void do_(int o,int l,int r){//区间长度减去原本1的个数即原本0的个数即翻转后1的个数cnt1[o]r-l1-cnt1[o];flip[o]!flip[o];}//初始化线段树 o是节点标记 从1开始 但是数组下标从0开始void build(vectorinta,int o,int l,int r){//只有一个元素直接求和if(lr){cnt1[o]a[l-1];return;}//分成区间求和int ml(r-l)/2;//左孩子标记为o*2 左区间为[l,m]build(a,o*2,l,m);//右孩子标记为o*21 右区间为[m1,r]build(a,o*21,m1,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(LlrR){do_(o,l,r);return;}//分而治之int ml(r-l)/2;//如果有标记则需要向下传递标记并且清空当前节点之前的标记情况if(flip[o]){do_(o*2,l,m);do_(o*21,m1,r);flip[o]false;}//左区间有交集if(mL)update(o*2,l,m,L,R);//右区间有交集if(mR)update(o*21,m1,r,L,R);//该节点区间和为左右孩子区间和之和maintain(o);}vectorlong long handleQuery(vectorint nums1, vectorint nums2, vectorvectorint queries) {int nnums1.size();build(nums1,1,1,n);vectorlong long res;long long sumaccumulate(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)sum1LL*q[1]*cnt1[1];elseres.push_back(sum);}return res;}
};总结https://oi-wiki.org/ds/seg/讲得很好
