当前位置: 首页 > news >正文

2023-07-26力扣每日一题-区间翻转线段树

链接:

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

题意:

给两个等长数组nums1和nums2,三个操作:

操作1:将nums1的[l,r]翻转(0变1,1变0)

操作2:将nums2[any]变成nums2[any]+nums1[any]*p,p由操作给出,any表示数组里的每一位

操作3:查询nums2的和

解:

由于每次更新nums2的时候,不需要考虑nums2[any]本身的值(基于nums2[any]增减,但增减多少不取决于nums2[any]),而且每次查询都查询整个nums2,所以只要维护一个nums2的和sum,不用考虑修改nums2

这样实际上我们只需要一颗区间翻转型线段树,节点设计:

struct Node
{int l,r,val;//左端点,右端点,值bool lazy;//区间翻转使用bool型懒标记即可Node():l(-1),r(-1),val(0),lazy(false) {}; //构造函数
};

然后就是设计线段树,4N空间:

struct SegTree
{vector<Node>SegNodes;//存储线段树节点vector<int>& nums;//设计了nums1的引用,方便类内访问nums1SegTree(vector<int> &nums1): nums(nums1)//绑定应用{SegNodes.resize(4*nums1.size());//4倍空间}
};

(下面都是类内函数)构建函数设计,使用递归求和,这边注意运算符优先级(n<<1)|1 和 n<<1|1一样,但是(n<<1)+2 和 n<<1+2不一样:

int Build(int n,int l,int r){//cout<<"Build"<<n<<ends<<l<<ends<<r<<endl; SegNodes[n].l=l;//设定这个节点 应有 的左端点SegNodes[n].r=r;//设定这个节点 应有 的右端点if(l==r) return SegNodes[n].val=nums[l];//当左端点等于右端点时,没有子节点,直接从num中取值else//有子节点{int mid=(l+r)/2;//区间中点SegNodes[n].val+=Build((n<<1)|1,l,mid);//左子节点SegNodes[n].val+=Build((n<<1)+2,mid+1,r);//右子节点return SegNodes[n].val;//返回求值结果}}

懒标记传递函数,每次使用该节点时且存在懒标记时才进行传递,对一段区间反复修改的时候不需要对最底层修改:

void pushdown(int n)//向下传递懒标记 {//cout<<"push_down"<<n<<endl; if(SegNodes[n].lazy)//存在懒标记{SegNodes[n].lazy=false;//移除当前懒标记 SegNodes[(n<<1)|1].lazy=!SegNodes[(n<<1)|1].lazy;//更新子节点标记SegNodes[(n<<1)|1].val=SegNodes[(n<<1)|1].r-SegNodes[(n<<1)|1].l+1-SegNodes[(n<<1)|1].val;SegNodes[(n<<1)+2].lazy=!SegNodes[(n<<1)+2].lazy;//更新子节点标记SegNodes[(n<<1)+2].val=SegNodes[(n<<1)+2].r-SegNodes[(n<<1)+2].l+1-SegNodes[(n<<1)+2].val;}}

区间修改函数,如果当前修改段包含整个区间,那么直接整个区间打上懒标记;如果不是包含整个区间,则对这个区间的左右子节点进行判断修改:

void change(int n,int l,int r){//cout<<"change"<<n<<ends<<l<<ends<<r<<endl; if(SegNodes[n].l>=l && SegNodes[n].r<=r)//包含整个区间 {SegNodes[n].lazy=!SegNodes[n].lazy;SegNodes[n].val=SegNodes[n].r-SegNodes[n].l+1-SegNodes[n].val;return;//直接修改+返回}pushdown(n);//看看该节点有没有需要传递的标记if(SegNodes[(n<<1)|1].r>=l) change((n<<1)|1,l,r);//查看左节点if(SegNodes[(n<<1)+2].l<=r) change((n<<1)+2,l,r);//查看右节点SegNodes[n].val=SegNodes[(n<<1)|1].val+SegNodes[(n<<1)+2].val;//更新父节点值}

区间查询函数,同样如果包含整个区间,直接返回值,否则查询左右子节点:

int query(int n,int l,int r){if(SegNodes[n].l>=l && SegNodes[n].r<=r) return SegNodes[n].val;if(SegNodes[n].r<l || SegNodes[n].l>r) return 0;pushdown(n);int ret=0;if(SegNodes[(n<<1)|1].r>=l) ret+=query((n<<1)|1,l,r);if(SegNodes[(n<<1)+2].l<=r) ret+=query((n<<1)+2,l,r);return ret;}

实际代码:

#include<bits/stdc++.h>
using namespace std;
struct Node
{int l,r,val;bool lazy;Node():l(-1),r(-1),val(0),lazy(false) {}; 
};
struct SegTree
{vector<Node>SegNodes;vector<int>& nums;SegTree(vector<int> &nums1): nums(nums1){SegNodes.resize(4*nums1.size());}void check(){cout<<"checkIng"<<endl;for(auto &SegNode:SegNodes){cout<<SegNode.l<<" "<<SegNode.r<<" "<<SegNode.val<<endl;cout<<"lazy:"<<SegNode.lazy<<endl; }cout<<"checkEnd"<<endl;}int Build(int n,int l,int r){//cout<<"Build"<<n<<ends<<l<<ends<<r<<endl; SegNodes[n].l=l;SegNodes[n].r=r;if(l==r) return SegNodes[n].val=nums[l];else{int mid=(l+r)/2;SegNodes[n].val+=Build((n<<1)|1,l,mid);SegNodes[n].val+=Build((n<<1)+2,mid+1,r);return SegNodes[n].val;}}void pushdown(int n)//向下传递懒标记 {//cout<<"push_down"<<n<<endl; if(SegNodes[n].lazy)//存在懒标记{SegNodes[n].lazy=false;//移除当前懒标记 SegNodes[(n<<1)|1].lazy=!SegNodes[(n<<1)|1].lazy;//更新子节点标记SegNodes[(n<<1)|1].val=SegNodes[(n<<1)|1].r-SegNodes[(n<<1)|1].l+1-SegNodes[(n<<1)|1].val;SegNodes[(n<<1)+2].lazy=!SegNodes[(n<<1)+2].lazy;//更新子节点标记SegNodes[(n<<1)+2].val=SegNodes[(n<<1)+2].r-SegNodes[(n<<1)+2].l+1-SegNodes[(n<<1)+2].val;}}void change(int n,int l,int r){//cout<<"change"<<n<<ends<<l<<ends<<r<<endl; if(SegNodes[n].l>=l && SegNodes[n].r<=r)//包含整个区间 {SegNodes[n].lazy=!SegNodes[n].lazy;SegNodes[n].val=SegNodes[n].r-SegNodes[n].l+1-SegNodes[n].val;return;}pushdown(n);if(SegNodes[(n<<1)|1].r>=l) change((n<<1)|1,l,r);if(SegNodes[(n<<1)+2].l<=r) change((n<<1)+2,l,r);SegNodes[n].val=SegNodes[(n<<1)|1].val+SegNodes[(n<<1)+2].val;}int query(int n,int l,int r){if(SegNodes[n].l>=l && SegNodes[n].r<=r) return SegNodes[n].val;if(SegNodes[n].r<l || SegNodes[n].l>r) return 0;pushdown(n);int ret=0;if(SegNodes[(n<<1)|1].r>=l) ret+=query((n<<1)|1,l,r);if(SegNodes[(n<<1)+2].l<=r) ret+=query((n<<1)+2,l,r);return ret;}
};
vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries)
{int lg=nums1.size();long long sum=0;vector<long long>ans;for(const auto &num2:nums2) sum+=num2;SegTree st(nums1);st.Build(0,0,lg-1);for(const auto &querie:queries){//st.check();switch(querie[0]){case 1:st.change(0,querie[1],querie[2]);break;case 2:sum+=(long long)st.query(0,0,lg-1)*querie[1];break;case 3:ans.push_back(sum);break;}}return ans;
}
int main()
{vector<vector<int>> queries;vector<int>nums1,nums2;int n1,n2,temp,temp0;cout<<"input n1 and n2 as size(nums1) and size(nums2)"<<endl; cin>>n1>>n2;while(n1--){cin>>temp;nums1.push_back(temp);}while(n2--){cin>>temp;nums2.push_back(temp);}cout<<"input n1 as size(queries)"<<endl; cin>>n1;while(n1--){cout<<"input mode key1 key2"<<endl;cin>>n2>>temp>>temp0;queries.push_back({n2,temp,temp0});}vector<long long>ans=handleQuery(nums1,nums2,queries);for(auto a:ans) cout<<a<<ends;cout<<endl;return 0;
}

限制:

  • 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

相关文章:

2023-07-26力扣每日一题-区间翻转线段树

链接&#xff1a; 2569. 更新数组后处理求和查询 题意&#xff1a; 给两个等长数组nums1和nums2&#xff0c;三个操作&#xff1a; 操作1&#xff1a;将nums1的[l,r]翻转&#xff08;0变1,1变0&#xff09; 操作2&#xff1a;将nums2[any]变成nums2[any]nums1[any]*p&…...

Java设计模式之 -- 桥接模式

什么是桥接模式 桥接模式是一种结构型设计模式&#xff0c;也被称为“Handle/Body”。这种设计模式主要用于将抽象部分与它的实现部分分离&#xff0c;使它们可以独立地变化。这种方式有助于减少系统中的耦合性&#xff0c;增加了扩展性。 主要解决什么问题 桥接模式主要解决…...

【node.js】02-path模块

目录 1. path.join() 2. path.basename() 3. path.extname() 1. path.join() 使用 path.join() 方法&#xff0c;可以把多个路径片段拼接为完整的路径字符串&#xff0c;语法格式如下&#xff1a; path.join([...paths]) 例子&#xff1a; const path require(path)co…...

攻防世界-Reverse-re1

题目描述&#xff1a;菜鸡开始学习逆向工程&#xff0c;首先是最简单的题目 下载附件&#xff0c;执行程序&#xff0c;如下界面 1. 思路分析 没啥说的&#xff0c;既然题目都说是一道简单的逆向题&#xff0c;那么直接使用ida逆向即可&#xff0c;看逆向出的结果是否能写入到…...

AES加密的基本常识和封装类

AES加密的基本常识和封装类 AES&#xff08;Advanced Encryption Standard&#xff09;是一种对称密钥加密算法&#xff0c;被广泛用于保护敏感数据的安全性。它是一种块加密算法&#xff0c;意味着它将明文数据分成固定大小的块&#xff0c;并使用相同的密钥对每个块进行独立…...

elasticsearch使用记录

参考文章&#xff1a;https://elasticsearch-py.readthedocs.io/en/v8.8.2/ 参考文章&#xff1a;https://cuiqingcai.com/6214.html 参考文章&#xff1a;https://www.cnblogs.com/cupleo/p/13953890.html elasticsearch版本&#xff1a;8.8.2(软件包发行版) python版本&#…...

UNI-APP_横屏切换竖屏出现样式混乱问题

app从竖屏页面1进入竖屏页面2&#xff0c;再进入横屏&#xff0c;再返回&#xff0c;再返回从新回到竖屏页面1&#xff0c;再次进入竖屏页面2&#xff0c;发现竖屏页面2的所有图片字体都被放大了。再返回竖屏1&#xff0c;再进入竖屏2&#xff0c;一切又恢复正常。 解决跳转横…...

数据可视化(3)

1.饼状图 #饼状图 #pie&#xff08;x,labels,colors,labeldistance,autopct,startangle,radius,center,textprops&#xff09; #x,每一块饼状图的比例 #labels:每一块饼形图外侧显示的文字说明 #labeldistance&#xff1a;标记的绘制位置&#xff0c;相对于半径的比例&#xf…...

AI面试官:MD5、DES、RSA、AES加密

AI面试官&#xff1a;MD5、DES、RSA、AES加密 文章目录 AI面试官&#xff1a;MD5、DES、RSA、AES加密1. 什么是MD5加密&#xff1f;它在实际应用中有哪些场景&#xff1f;2. DES加密是什么&#xff1f;它在现实中的应用场景有哪些&#xff1f;3. 问题&#xff1a;RSA加密是什么…...

Shell脚本学习-$$特殊变量

$$特殊变量&#xff1a; 获取脚本执行的进程号&#xff08;PID&#xff09;。 [rootvm1 scripts]# cat test_pid.sh echo $$ > /tmp/a.pid sleep 300代码说明&#xff1a; 1&#xff09;获取$$值&#xff0c;也就是当前脚本进程的PID值&#xff0c;重定向到/tmp/a.pid文件…...

vscode中python插件过新导致无法正常debug问题解决安装vscode以前版本python插件教程

您需要从.vsix文件安装它。您可以在此处找到它们。 下载所需.vsix版本的文件。您可能需要单击assets才能看到它们。 然后打开 VSCode&#xff0c;转到extensions-> 单击三个点 ->install from vsix并选择您的文件。 重启以后&#xff0c;就可以正常debug了&#xff01;...

chrome macos编译

下载工具包 git clone https://chromium.googlesource.com/chromium/tools/depot_tools/gitpwd export PATH"$PATH:/Users/lichengjun/Downloads/chrome_build/depot_tools" mkdir chromium cd chromium 如果想快的话直接: fetch --nohooks --no-history chromium (…...

Linux环境下Elasticsearch相关软件安装

Linux环境下Elasticsearch相关软件安装 本文将介绍在linux(Centos7)环境下安装Elasticsearch相关的软件。 1、安装Elasticsearch 1.1 Elasticsearch下载 首先去Elasticsearch官网下载相应版本的安装包&#xff0c;下载之后传输到linux服务器上。 官网地址&#xff1a;http…...

【趟坑记录】d3.zoom()的正确使用姿势 @d3.v7

【趟坑记录】d3.zoom()的正确使用姿势 d3.v7 文章目录 【趟坑记录】d3.zoom()的正确使用姿势 d3.v7问题重现原因分析解决方案放缩平移写法特殊修改transform函数的写法 总结 在开发一个D3应用的时候遇到了一个 zoom相关的问题&#xff0c;记录解决思路与方案 问题重现 最近在…...

基于 Docker + Nginx + Gitlab-runner 实现前端自动化部署流程

本篇会用到Docker&#xff0c;Gitlab-runner等相关工具&#xff0c;如果对其不是特别了解&#xff0c;可以参考下相关文档&#xff1a; GitLab RunnerDocker 快速入门CI/CD&#xff1a;持续集成/持续部署 在早期部署前端项目时&#xff0c;我们通常会通过ftp把前端代码直接传…...

make/makefile的使用

make/makefile 文章目录 make/makefile初步认识makefile的工作流程依赖关系和依赖方法make的使用 总结 make是一个命令&#xff0c;是一个解释makefile中指令的命令工具&#xff0c;makefile是一个文件&#xff0c;当前目录下的文件&#xff0c;两者搭配使用&#xff0c;完成项…...

Flutter中Navigator 跳转传参数和反向传参数

初始化路由 MaterialApp(routes: <String, WidgetBuilder>{"/Second": (BuildContext context){return Second("");}}, 跳转传参数 String va await Navigator.of(context).push(MaterialPageRoute(builder: (content) {return Second( demo); },…...

kettle开发-Day40-AI分流之case/switch

前言&#xff1a; 前面我们讲到了很多关于数据流的AI方面的介绍&#xff0c;包括自定义组件和算力提升这块的&#xff0c;今天我们来学习一个关于kettle数据分流处理非常重要的组件Switch / Case 。当我们的数据来源于类似日志、csv文件等半结构化数据时&#xff0c;我们需要在…...

MySQL下载与安装

MySQL下载与安装 一、下载 地址&#xff1a;https://dev.mysql.com/downloads/mysql/ 当前最新是8.0版本&#xff0c;我选择上一个最新的mysql-5.7.24-winx64.zip 二、安装 MySQL安装文件分两种 .msi和.zip &#xff0c;.msi需要安装 zip格式是自己解压&#xff0c;解压缩之后…...

c++基础2

文件操作 程序运行时产生的数据属于临时数据&#xff0c;程序一旦运行结束都会被释放 通过文件可以将数据持久化 c中对文件操作需要包含 文件类型分为两种 文本文件&#xff1a;文件以ASCII码形式存储在计算机中二进制文件&#xff1a;文件以文本的二进制存储在计算机中&a…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...