[蓝桥杯学习] 树状数组的二分

要解决这个问题,插入和删除可以用STL实现,2操作如果用树状数组实现的话,将数的值作为树状数组的下标,即值域。

树状数组有两种操作,一个是更新某点的值,另一个是求区间和。

mid = (l+r)/2 ,求和 t[a+1] 到 t[mid] ,设为x,如果x小于k,就mid右移,如果x大于k,就mid左移

二分查找的代码

注意:不同点是,可能第k大的数 c 到第 k+1 大的数 b之间都是到a求和有k个值,所以我们要找左边界,不断更新ans,遇到相等的,先记录下来,然后把mid左移。

int find(int a,int k)
{int l = a+1; int r = maxn;int mid;int ans=-1;while(l <= r){mid = (l+r) >> 1;if(query(mid) - query(a) = k) ans = mid;if(query(mid) - query(a) >= k) r = mid-1;else l = mid+1; }return ans;
}

例题

第i个小朋友前面有ai个小朋友,如果后面没有比他低的,那么他的身高是 ai+1

如果我们从前往后遍历数组a[i] ,我们是无法知道后面小朋友的身高,所以要从后往前遍历,但是,计算中间小朋友的身高时,还是得知道后面有多少人比他低。

使用树状数组时,从后往前遍历时,每确定一个身高,就把该下标从1变为0,这样,往前计算小朋友身高时,通过求和,就能得到这个小朋友的身高,例:原本是111111,两次删除之后是100111,ai=3的小朋友,ai+1=4,但是很明显,确定身高的小朋友都比他低,所以要后移两位(通过0的存在实现了),移到了6

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/234213.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

气缸功能块(SMART PLC梯形图代码)

有关气缸功能块的更多介绍,可以参考下面链接文章: https://rxxw-control.blog.csdn.net/article/details/125459568https://rxxw-control.blog.csdn.net/article/details/125459568CODESYS平台双通气缸功能块 https://rxxw-control.blog.csdn.net/article/details/12544822…

TypeScript 和 jsdom 库创建爬虫程序示例

TypeScript 简介 TypeScript 是一种由微软开发的自由和开源的编程语言。它是 JavaScript 的一个超集&#xff0c;可以编译生成纯 JavaScript 代码。TypeScript 增加了可选的静态类型和针对对象的编程功能&#xff0c;使得开发更加大规模的应用容易。 jsdom 简介 jsdom 是一个…

第10课 实现多对多音视频会议功能

本课对应文件下载链接&#xff08;非源码&#xff09;&#xff1a;https://download.csdn.net/download/XiBuQiuChong/88717642 在前两节课&#xff0c;我们将推流端与播放端合并为一对一音视频聊天功能并解决了关键的回声问题&#xff0c;在此基础上&#xff0c;我们可以进一…

1876_电感的特性小结

Grey 全部学习内容汇总&#xff1a; GitHub - GreyZhang/g_hardware_basic: You should learn some hardware design knowledge in case hardware engineer would ask you to prove your software is right when their hardware design is wrong! 1876_电感的特性小结 主要是…

无法找到 WindowsKernelModeDriver10.0 的生成工具

无法找到 WindowsKernelModeDriver10.0 的生成工具(平台工具集 “WindowsKernelModeDriver10.0”)。若要使用 WindowsKernelModeDriver10.0 生成工具进行生成&#xff0c;请安装 WindowsKernelModeDriver10.0 生成工具。或者&#xff0c;可以升级到当前 Visual Studio 工具&…

2024年,前端必会的console骚操作

调试。程序员们努力地避免的东西,只为在代码中制造更多的错误。 编写无错误的代码是即使是最好的程序员也会觉得难以实现的。这就是为什么你应该总是调试代码。 而调试JavaScript代码的最好方法之一就是了不起的console.log()。除此之外,还有更好的方法。 这也正是本文的重点…

基于apache的http文件服务配置

背景&#xff1a; 公司的产品使用的第三方模组可以OTA&#xff0c;厂家提供的是window开启软件&#xff0c;这样就可以在本机做http下载服务器&#xff0c;然后使用端口映射的方式&#xff0c;公开到外网&#xff0c;这样就可以进行4G网络访问内网服务器了。但这个有个弊端&am…

【算法每日一练]-dfs bfs(保姆级教程 篇8 )#01迷宫 #血色先锋队 #求先序排列 #取数游戏 #数的划分

目录 今日知识点&#xff1a; 使用并查集映射点&#xff0c;构造迷宫的连通块 vis计时数组要同步当回合的处理 递归求先序排列 基于不相邻的取数问题&#xff1a;dfs回溯 n个相同球放入k个相同盒子&#xff1a;dfs的优化分支暴力 01迷宫 血色先锋队 求先序排列 取数游…

Unity添加所有场景到BuildSettings

Unity添加所有场景到BuildSettings using UnityEngine; using UnityEditor; using System.Collections.Generic; using System.IO; public class Tools : Editor {[MenuItem("Tools/添加所有场景到BuildSettings")]static void CheckSceneSetting(){List<string&…

BOM,JS执行机制等

1.BOM 概述 1.1什么是 BOM BOM( Browser Object Model &#xff09;即浏览器对象模型&#xff0c;它提供了独立于内容而与浏览器窗口进行交互的对象&#xff0c;其核心对象是window. BOM由一系列相关的对象构成&#xff0c;并且每个对象都提供了很多方法与属性。 BOM缺乏标…

十九:爬虫最终篇-平安银行商城实战

平安银行商场实战 需求 获取该商城商品信息 目标网址 https://m.yqb.com/bank/product-item-50301196.html?mcId1583912328849970&loginModepab&historyy&sceneModem&traceid30187_4dXJVel1iop详细步骤 1、寻找数据接口 2、对比payload寻找可疑参数 3、多…

系列十四、while do...while switch模板代码

一、while & do...while & switch模板代码 1.1、while /*** 需求&#xff1a;使用while循环打印5遍Hello World!*/ Test public void print5() {int i 1;while (i < 5) {System.out.println("Hello World! " LocalDateTime.now());// 线程休眠&#x…

大模型笔记【2】 LLM in Flash

Apple最近发表了一篇文章&#xff0c;可以在iphone, MAC 上运行大模型&#xff1a;【LLM in a flash: Efficient Large Language Model Inference with Limited Memory】。 主要解决的问题是在DRAM中无法存放完整的模型和计算&#xff0c;但是Flash Memory可以存放完整的模型。…

05、Kafka ------ 各个功能的作用解释(主题和分区 详解,用命令行和图形界面创建主题和查看主题)

目录 CMAK 各个功能的作用解释&#xff08;主题&#xff09;★ 主题★ 分区★ 创建主题&#xff1a;★ 列出和查看主题 CMAK 各个功能的作用解释&#xff08;主题&#xff09; ★ 主题 Kafka 主题虽然也叫 topic&#xff0c;但它和 Pub-Sub 消息模型中 topic 主题及 AMQP 的 t…

【实用技巧】Windows 电脑向iPhone或iPad传输视频方法1:无线传输

一、内容简介 本文介绍如何使用 Windows 电脑向 iPhone 或 iPad 传输视频&#xff0c;以 iPhone 为例&#xff0c;iPad的操作方法类似&#xff0c;本文不作赘述。 二、所需原材料 Windows 电脑&#xff08;桌面或其它文件夹中存有要导入的视频&#xff09;、iPhone 14。 待…

如何通过PreMaint状态监测发现设备故障:以振动监测为例

在现代工业环境中&#xff0c;设备的健康状况对于维持生产效率至关重要。计划外停机可能导致巨大的成本损失&#xff0c;因此采用先进的监测技术成为预防性维护的核心策略之一。其中&#xff0c;振动监测作为一种早期故障检测手段&#xff0c;通过PreMaint状态监测系统的引入&a…

从虚拟到现实:数字孪生驱动智慧城市可持续发展

随着科技的飞速发展&#xff0c;智慧城市已经成为未来城市发展的重要趋势。数字孪生技术作为智慧城市建设中的关键技术之一&#xff0c;正在发挥着越来越重要的作用。本文将探讨数字孪生如何从虚拟走向现实&#xff0c;驱动智慧城市的可持续发展。 一、数字孪生技术&#xff1…

解决sublime中文符号乱码问题

效果图 原来 后来 问题不是出自encode文件编码&#xff0c;而是win10的字体问题。 解决方法 配置&#xff1a; { "font_face":"Microsoft Yahei", "dpi_scale": 1.0 } 参考自 Sublime 输入中文显示方框问号乱码_sublime中文问号-CSDN博…

【开源】基于JAVA+Vue+SpringBoot的大学计算机课程管理平台

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 实验课程档案模块2.2 实验资源模块2.3 学生实验模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 实验课程档案表3.2.2 实验资源表3.2.3 学生实验表 四、系统展示五、核心代码5.1 一键生成实验5.2 提交实验5.3 批阅实…

系列十四、理解MySQL varchar(50)

一、理解MySQL varchar(50) 1.1、概述 日常开发中&#xff0c;数据库建表是必不可少的一个环节&#xff0c;建表的时候通常会看到设定某个字段的长度为varchar(50)&#xff0c;例如如下建表语句&#xff1a; 那么怎么理解varchar(50)&#xff1f;这个分情况的&#xff0c;MySQ…