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

线段树合并

前置知识:权值线段树,动态开点。

引入

我们先来看一道题:

永无乡包含 nnn 座岛,给出每座岛的重要度的排名,名次用 111nnn 来表示。一开始有 mmm 条边连接,接下来有 qqq 次操作。操作分两种:

  • B x y 表示在岛与岛之间修建一座新桥。
  • Q x k 表示询问当前与岛连通的所有岛中第重要的是哪座岛。

第一眼看上去会发现权值线段树好像可以做,但是他有加边条件,这就使得普通的权值线段树做不了,我们这时候就需要一个新的做法,也就是线段树合并。

思路

线段树合并的一个重要前提就是你们根节点的区间是相同的。

我们合并两棵线段树其实就相当于将一棵线段树的信息附在另一棵线段树上面。

我们假设我们要合并线段树 AAA 和线段树 BBB ,且把线段树 BBB 的信息附在线段树 AAA 上。

我们可以从根节点同时往下枚举,分以下几种情况。

  • 如果这个点线段树 AAA 和线段树 BBB 都有,那么我们继续往下枚举。
  • 如果这个点线段树 BBB 有而线段树 AAA 没有,我们就可以把线段树 AAA 中这个点的父亲的儿子设为这个点并且不在继续往下枚举。
  • 如果这个点线段树 AAA 有而线段树 BBB 没有,我们就可以不再往下枚举。
  • 如果这个点线段树 AAA 和线段树 BBB 都没有,我们也可以不用再往下枚举了。

到此,我们线段树就合并完了。

代码

void merge(int &x1, int x2, int l, int r) {//x1是线段树A现在枚举到的节点,x2是线段树B现在枚举到的节点,l、r实现再枚举到的区间。if (!x1 || !x2)//如果这个节点线段树A没有或者线段树B没有x1 = x1 + x2;//因为这两个点至少一个是0,所以他们的和就是另外一个点。else {int mid = (l + r) / 2;merge(tree[x1].lson, tree[x2].lson, l, mid);merge(tree[x1].rson, tree[x2].rson, mid + 1, r);updata(x1);//记得合并完后要更新这个节点}
}

例题

  • 永无乡:洛谷
  • [USACO17JAN]Promotion Counting P:洛谷

相关文章:

线段树合并

前置知识:权值线段树,动态开点。 引入 我们先来看一道题: 永无乡包含 nnn 座岛,给出每座岛的重要度的排名,名次用 111 到 nnn 来表示。一开始有 mmm 条边连接,接下来有 qqq 次操作。操作分两种&#xff…...

研发效能 | DevOps如何改变游戏公司工作方式?

如果你是游戏开发者,那么在过去几年里,你可能会觉得有人给了你一把双刃剑。 整个行业不断蓬勃发展,但玩家的预期值也越来越高。玩家们总是希望游戏体验能够更快、更真实、更具创造性。此外,他们还希望能够定期推出新的游戏和更新…...

Mongo聚合和Springboot整合Mongo聚合

聚合(aggregate)是基于数据处理的聚合管道,每个文档通过一个由多个阶段(stage)组成的管道,可以对每个阶段的管道进行分组、过滤等功能,然后经过一系列的处理,输出相应的结果。 语法格式:db.集合名称.aggregate({管道:{表达式}}) 常用管道如下: $group: 将集合中的⽂…...

第06章_索引的数据结构

第06章_索引的数据结构 🏠个人主页:shark-Gao 🧑个人简介:大家好,我是shark-Gao,一个想要与大家共同进步的男人😉😉 🎉目前状况:23届毕业生,目…...

不确定的市场,确定的增长,海尔智家2022全球再逆增

文|螳螂观察 作者| 余一 上市公司2022年年报逐渐进入密集披露期,在当前的年报季窗口,各家公司的业绩情况被高度关注。 3月30日晚,海尔智家发布了2022年财报。财报显示,2022年海尔智家实现收入2435.14亿元,同比增长7…...

测试老鸟手把手教你python接口自动化测试项目实战演示

目录 前言 一、项目准备 二、项目流程 三、完整代码 四、总结 前言 在进行接口自动化测试项目实战之前,我们需要先了解什么是接口自动化测试。接口自动化测试是通过自动化脚本模拟用户请求和服务器响应的过程,以检测接口是否符合预期,确…...

一起来学5G终端射频标准(Coherent UL-MIMO测试要求)

01 — Coherent UL-MIMO测试要求 首先什么是Coherent?它的英文释义是:(of ideas, thoughts, argument, theory, or policy) logical and consistent,翻译过来就是:(看法、思想、论证、理论或政策等&…...

计算广告(五)

Nobid Nobid(在某手有时也叫MCB,在Facebook叫Lowest Cost)是指广告主不用(也不能)对转化成本进行出价,而是出一个预算(大多数是日预算),然后投放平台的目标是在时间范围…...

排序输入的高效霍夫曼编码 | 贪心算法 3

前面我们讲到了 贪心算法的哈夫曼编码规则,原理图如下: 如果我们知道给定的数组已排序(按频率的非递减顺序),我们可以在 O(n) 时间内生成霍夫曼代码。以下是用于排序输入的 O(n) 算法。1.创建两个空队列。2.为每个唯一…...

奇异值分解(SVD)和图像压缩

在本文中,我将尝试解释 SVD 背后的数学及其几何意义,还有它在数据科学中的最常见的用法,图像压缩。 奇异值分解是一种常见的线性代数技术,可以将任意形状的矩阵分解成三个部分的乘积:U、S、V。原矩阵A可以表示为&#…...

Java如何从yml文件获取对象

目录一、背景二、application.yml三、ChinaPersonFactory.java四、使用示例一、背景 在 SpringBoot 中,我们可以使用 Value 注解从属性文件(例如 application.yml 或 application.properties)中获取配置信息,但是只能获取简单的字…...

vue使用tinymce实现富文本编辑器

安装两个插件tinymce和 tinymce/tinymce-vue npm install tinymce5.10.3 tinymce/tinymce-vue5.0.0 -S 注意: tinymce/tinymce-vue 是对tinymce进行vue的包装,主要作用当作vue组件使用-S保存到package.json文件 2. 把node_modules/tinymce下的目录&a…...

yolov4实战训练数据

1、克隆项目文件 项目Github地址:https://github.com/AlexeyAB/darknet 打开终端,克隆项目 git clone https://github.com/AlexeyAB/darknet.git无法克隆的话,把https修改为git git clone git://github.com/AlexeyAB/darknet.git修改Makef…...

第十四章 DOM的Diff算法与key

React使用Diff算法来比较虚拟DOM树和真实DOM树之间的差异,并仅更新必要的部分,以提高性能。key的作用是在Diff算法中帮助React确定哪些节点已更改,哪些节点已添加或删除。 我们以案例来说明。 使用索引值和唯一ID作为key的效果 1、使用索引…...

MySQL调优

MySQL调优常见的回答如何回答效果更好业务层的优化如果只能用mysql该如何优化代码层的优化SQL层面优化总结常见的回答 SQL层面的优化——创建索引,创建联合索引,减少回表。再有就是少使用函数查询。 回表指的是数据库根据索引(非主键&#…...

《Flutter进阶》flutter升级空安全遇到的一些问题及解决思路

空安全出来挺久了,由于业务需求较紧,一直没时间去升级空安全,最近花了几天去升级,发现其实升级也挺简单的,不要恐惧,没有想象中的多BUG。 flutter版本从1.22.4升到3.0.5; compileSdkVersion从1…...

最值得入手的五款骨传导耳机,几款高畅销的骨传导耳机

骨传导耳机是一种声音传导方式,主要通过颅骨、骨骼把声波传递到内耳,属于非入耳式的佩戴方式。相比传统入耳式耳机,骨传导耳机不会堵塞耳道,使用时可以开放双耳,不影响与他人的正常交流。骨传导耳机不会对耳朵产生任何…...

HashMap源码分析 (1.基础入门) 学习笔记

本章为 《HashMap全B站最细致源码分析课程》 拉钩教育HashMap 学习笔记 文章目录1. HashMap的数据结构1. 数组2. 链表3. 哈希表3.1 Hash1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。 1. 数组 在生成数组的时候数…...

6 使用强制类型转换的注意事项

概述 在C语言中,强制类型转换是通过直接转换为特定类型的方式来实现的,类似于下面的代码。 float fNumber = 66.66f; // C语言的强制类型转换 int nData = (int)fNumber; 这种方式可以在任意两个类型间进行转换,太过随意和武断,很容易带来一些难以发现的隐患和问题。C++为…...

Leetcode.939 最小面积矩形

题目链接 Leetcode.939 最小面积矩形 Rating : 1752 题目描述 给定在 xy平面上的一组点,确定由这些点组成的矩形的最小面积,其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形,就返回 0。 示例 1: 输入&#xff1…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...