【数据结构1-2】P5076 普通二叉树(简化版)(c++,multiset做法)
文章目录
- 一、题目
- 【深基16.例7】普通二叉树(简化版)
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 基本思路:
一、题目
【深基16.例7】普通二叉树(简化版)
题目描述
您需要写一种数据结构,来维护一些数( 都是 1 0 9 10^9 109 以内的数字)的集合,最开始时集合是空的。其中需要提供以下操作,操作次数 q q q 不超过 1 0 4 10^4 104:
- 查询 x x x 数的排名(排名定义为比当前数小的数的个数 + 1 +1 +1。若有多个相同的数,应输出最小的排名)。
- 查询排名为 x x x 的数。
- 求 x x x 的前驱(前驱定义为小于 x x x,且最大的数)。若未找到则输出 − 2147483647 -2147483647 −2147483647。
- 求 x x x 的后继(后继定义为大于 x x x,且最小的数)。若未找到则输出 2147483647 2147483647 2147483647。
- 插入一个数 x x x。
输入格式
第一行是一个整数 q q q,表示操作次数。
接下来 q q q 行,每行两个整数 o p , x op,x op,x,分别表示操作序号以及操作的参数 x x x。
输出格式
输出有若干行。对于操作 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4,输出一个整数,表示该操作的结果。
样例 #1
样例输入 #1
7
5 1
5 3
5 5
1 3
2 2
3 3
4 3
样例输出 #1
2
3
1
5
基本思路:
- 题目中提到了集合、而且是维护一些数的集合,我想到了STL中的set(底层是平衡树的一种),不过集合元素中右重复的元素,需要用到multiset,可以存放重复的元素并且时升序排序的。
- 对于操作1,查询x的排名,应为set不支持随机访问,所以需要从头遍历一个一个数,需要注意的是”有多个相同的数,应输出最小的排名“,所以遍历到第一个等于x的数break即可。
- 操作2,同1,遍历集合。
- 操作3,再找前驱和后继之前需要初始化一下multiset ,给出一个边界。找x的前驱,用到了STL自带的二分查找lower_bound,返回第一个大于等于x的迭代器。
- 操作4,使用upper_bound,返回第一个大于x的迭代器,取值后即是x的后继。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII;
const int N = 1000010;
multiset<int> s;
const int INF = 2147483647;void solve(){int op,x;cin>>op>>x;if(op==1){//查询x数的排名int num=0;for(auto i:s)if(i<x) num++;//注意是<else break;cout<<num<<endl;}else if(op==2){//查询排名为x的数int num=-1;for(auto i:s){num++;if(num==x){cout<<i<<endl;break;}}}else if(op==3){//x的前驱cout<<*(--s.lb(x))<<endl;}else if(op==4){//x的后继cout<<*(s.ub(x))<<endl;}else{//将x插入集合s.insert(x);}}signed main(){IOS;int T=1;cin>>T;s.insert(INF),s.insert(-INF);while(T--){solve();}return 0;
}
相关文章:
【数据结构1-2】P5076 普通二叉树(简化版)(c++,multiset做法)
文章目录 一、题目【深基16.例7】普通二叉树(简化版)题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路: 一、题目 【深基16.例7】普通二叉树(简化版) 题目描述 您需要写一种数据结构,来维…...
Linux系统安装及管理
目录 一、Linux应用程序基础 1.1应用程序与系统命令的关系 1.2典型应用程序的目录结构 1.3常见的软件包装类型 二、RPM软件包管理 1.RPM是什么? 2.RPM命令的格式 2,1查看已安装的软件包格式 2.2查看未安装的软件包 3.RPM安装包从哪里来? 4.挂…...
MySQL学生向笔记以及使用过程问题记录(内含8.0.34安装教程
MySQL 只会写代码 基本码农 要学好数据库,操作系统,数据结构与算法 不错的程序员 离散数学、数字电路、体系结构、编译原理。实战经验, 高级程序员 去IOE:去掉IBM的小型机、Oracle数据库、EMC存储设备,代之以自己在开源…...
obs video-io.c
video_frame_init 讲解 /* messy code alarm video_frame_init 函数用于初始化视频帧。它接受一个指向 struct video_frame 结构体的指针 frame, 视频格式 format,以及宽度 width 和高度 height。该函数根据视频格式的不同,计算出每个视频帧…...
简述 tcp 和 udp的区别?
简述 tcp 和 udp的区别? TCP(Transmission Control Protocol)和UDP(User Datagram Protocol)是两种不同的传输层协议,用于在计算机网络中进行数据传输。以下是它们的主要区别: 区别࿱…...
信息收集 - 谷歌hack
搜索引擎 FOFA网络空间测绘:https://fofa.info/ FOFA(FOcus on Assets)是一个网络空间搜索引擎,可以帮助用户快速定位和收集特定目标的信息。 ZoomEye:https://www.zoomeye.org ZoomEye 是一个网络空间搜索引擎,可以用于发现和收集特定目标的网络设备、Web应用程序、开放…...
英飞凌TC3xx之一起认识DSADC系列(七)应用实战项目二(实现旋变软解码)
英飞凌TC3xx之一起认识DSADC系列(七) 1 项目要求2 项目实现2.1 内部时钟配置2.2 输入信号配置2.3 调制器配置2.4 滤波器链路配置2.5 整流器配置3 总结本文写一篇关于DSADC的resover的载波信号生成的应用,刚刚接触DSADC的开发者很容易被手册中简短的文字描述弄的迷惑,它到底…...
【浏览器】同源策略和跨域
1. 什么是跨域 在说跨域之前,先说说同源策略,什么是同源策略呢?同源策略是浏览器的一种安全机制,减少跨站点脚本攻击(XSS,Cross Site Scripting)、跨站点请求伪造(CSRF,Cross Site Request Forgery)攻击等,因为非同源的请求会被浏览器拦截掉。 同源就是协议、域名(…...
云计算与大数据之间的羁绊(期末不挂科版):云计算 | 大数据 | Hadoop | HDFS | MapReduce | Hive | Spark
文章目录 前言:一、云计算1.1 云计算的基本思想1.2 云计算概述——什么是云计算?1.3 云计算的基本特征1.4 云计算的部署模式1.5 云服务1.6 云计算的关键技术——虚拟化技术1.6.1 虚拟化的好处1.6.2 虚拟化技术的应用——12306使用阿里云避免了高峰期的崩…...
基于jdk11和基于apache-httpclient的http请求工具类
1.基于apache-httpclient 需要引入依赖 <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId><version>4.3.5</version></dependency> 工具类如下: package com.bw.e…...
Node.js(二)-模块化
1. 模块化的基本概念 1.1 什么是模块化 模块化是指解决一个复杂问题时,自顶向下逐层将系统拆分成若干模块的过程。对于整个系统来说,模块是可组合、分解和更换的单元。 1.2 编程领域中的模块化 编程领域中的模块化,就是遵守固定的规则&…...
ARM AArch64的TrustZone架构详解(上)
目录 一、概述 1.1 在开始之前 二、什么是TrustZone? 2.1 Armv8-M的TrustZone 2.2 Armv9-A Realm Management Extension(RME)...
从源PC上一次性p2v(qcow2)的构想
磁盘分区表,虚拟硬盘文件,操作系统引导 1. 基本概念和术语 源硬盘:一般就是客户的PC机的硬盘,硬盘里面包含了Windows分区。 源Windows:以源硬盘启动的Windows环境。 虚拟磁盘文件:文件格式有qcow2、vhd…...
数据结构:KMP算法
1.何为KMP算法 KMP算法是由Knuth、Morris和Pratt三位学者发明的,所以取了三位学者名字的首字母,叫作KMP算法。 2.KMP的用处 KMP主要用于字符串匹配的问题,主要思想是当出现字符串不匹配时,我们可以知道一部分之前已经匹配过的的文…...
小程序真机如何清除订阅数据
在做小程序订阅消息开发的过程中发现,真机上如果是选择了‘总是保持以上选择’,一旦用户授权后,后面就不会再弹出申请改订阅消息的授权弹窗,这对于开发过程中是很不方便的。 曾试过清除缓存,重进小程序也不能清除掉 解…...
基于ssm出租车管理系统的设计与实现论文
摘 要 现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本出租车管理系统就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完毕庞大的数据信息&…...
音视频转码
音视频转码是指: 容器中音视频数据编码方式转换,如由H.264编码转成mpeg-4编码,mp3转成AAC;音视频码率的转换,如4Mb视频码率降为2Mb,视频分辨率的转换,如1080P转换为720P,音频重采样…...
编解码异常分析
前言 最近在做的项目,有H264解码的需求。部分H264文件解码播放后,显示为绿屏或者花屏。 分析 如何确认是否是高通硬解码的问题 adb 指令 adb root adb remount adb shell setenforce 0 adb shell setprop vendor.gralloc.disable_ubwc 1 adb shell c…...
APISpace 热门好用的API推荐,含免费次数
短信验证码:可用于登录、注册、找回密码、支付认证等等应用场景。支持三大运营商,3秒可达,99.99%到达率,支持大容量高并发。通知短信:短信通知支持三大运营商以及虚拟运营商,我们提供电信级运维…...
Qt/QML编程学习之心得:一个.qml文件调用另一个.qml文件(十七)
在c++中,一个文件调用另外一个文件最直接最快捷的方式就是#incldue<头文件>的使用,那么在元数据描述性语言QML中,如何从一个界面描述调用另外一个界面描述,一个.qml文件调用另外一个.qml呢?QML虽然有个import,但是用法可以说完全不同于#include。 引用方法1:直接…...
C++_单列模式介绍
介绍 (1)…什么是单例 1.只能有一个实例化的对象的类(2).单例有什么用 1.多线程的线程池的设计 2.系统中只需要一个窗口时才使用单例(无法重复创建) 3.一个操作系统只能有一个文件系统(3).单例怎么用 1.隐藏所有构造函数 2.静态成员内部调用构造函数实例化 3.提供一个静态函数来…...
油烟净化器如何做到高效净化?科技力量,清新餐饮生活
我最近分析了餐饮市场的油烟净化器等产品报告,解决了餐饮业厨房油腻的难题,更加方便了在餐饮业和商业场所有需求的小伙伴们。 油烟净化器的出现,为我们的餐饮生活注入了一抹清新的色彩。然而,它究竟是如何工作的?为何能…...
【HTML5】HTML5 语音合成
一、前言 前一段时间在项目中需要用到播报文字语音。找到了 HTML 5 有这样的功能。 现在有时间进行总结下。 二、SpeechSynthesis SpeechSynthesis 接口是语音服务的控制接口。它可以用于获取设备上关于可用的合成声音的信息, 开始、暂停语音,或者别…...
顺序表的实现
目录 一. 数据结构相关概念 二、线性表 三、顺序表概念及结构 3.1顺序表一般可以分为: 3.2 接口实现: 四、基本操作实现 4.1顺序表初始化 4.2检查空间,如果满了,进行增容编辑 4.3顺序表打印 4.4顺序表销毁 4.5顺…...
深度学习中的池化
1 深度学习池化概述 1.1 什么是池化 池化层是卷积神经网络中常用的一个组件,池化层经常用在卷积层后边,通过池化来降低卷积层输出的特征向量,避免出现过拟合的情况。池化的基本思想就是对不同位置的特征进行聚合统计。池化层主要是模仿人的…...
Java面试整理-Java设计模式
Java中的设计模式通常是从更广泛的面向对象设计模式中借鉴而来的,这些模式旨在解决特定的设计问题和改善代码的可维护性、灵活性和可扩展性。设计模式大致可以分为三类:创建型、结构型和行为型。以下是这三类中一些常见的设计模式: 创建型模式 单例模式(Singleton):确保一…...
用CHAT了解更多知识点
问CHAT:什么是硅基生命和碳基生命? CHAT回复:硅基生命和碳基生命是两种理论性的生物体类型,这些生物体主要是由硅或碳元素以及其他元素构成的。 碳基生命是我们当前所熟知的生命形式。碳元素能够形成稳定且复杂的分子,…...
一个利用摸鱼时间背单词的软件
大家好,我是 Java陈序员。 最近进入了考试季,各种考试,英语四六级、考研、期末考等。不知道大家的英语四六级成绩怎么样呢? 记得大学时,英语四级都是靠高中学习积累的老本才勉强过关。 而六级则是考了多次ÿ…...
Matlab/Simulink的一些功能用法笔记(3)
01--引言 最近加入到一个项目组,有一些测试需要去支持,通过了解原先团队的测试方法后,自己作了如下改善,大大提高了工作效率。这也许就是软件开发的意义吧,能够去除一些重复的机械的人工操作并且结果还非常不可靠。 …...
Wafer晶圆封装工艺介绍
芯片封装的目的(The purpose of chip packaging): 芯片上的IC管芯被切割以进行管芯间连接,通过引线键合连接外部引脚,然后进行成型,以保护电子封装器件免受环境污染(水分、温度、污染物等)&…...
Mac OS 13+,Apple Silicon,删除OBS虚拟摄像头(virtual camera),
原文链接: https://www.reddit.com/r/MacOS/comments/142cv OBS为了捕获摄像头视频,将虚拟摄像头插件内置为系统插件了.如下 直接删除没有权限的,要删除他,在mac os 13以后,需要关闭先关闭苹果系统的完整性保护(SIP) Apple 芯片(M1,....)的恢复模式分为两种,回退恢复模式,和…...
精解 ES6 Promise 用法
🐱 个人主页:SHOW科技,公众号:SHOW科技 🙋♂️ 作者简介:2020参加工作,专注于前端各领域技术,共同学习共同进步,一起加油呀! 💫优质专栏&#x…...
Linux之基础I/O
目录 一、C语言中的文件操作 二、系统文件操作I/O 三、文件描述符fd 1、文件描述符的引入 2、对fd的理解 3、文件描述符的分配规则 四、重定向 1、重定向的原理 2、重定向的系统调用dup2 五、Linux下一切皆文件 一、C语言中的文件操作 1、打开和关闭 在C语言的文…...
Linux开发工具——gcc篇
gcc的使用 文章目录 gcc的使用 历史遗留问题(普通用户sudo) gcc编译过程 预处理(进行宏替换) 编译(生成汇编) 汇编(生成机器可识别代码) 链接(生成可执行文件或库文件&a…...
C#通讯——关于Winform中的简单的Http服务器与客户端
C#通讯——关于Winform中的简单的Http服务器与客户端 前言一、Http是什么?二、简单的Http服务器三、简单的Http客户端四、实际调用五、Winform中Http服务器和WebApi的区别? 前言 在实际项目中通讯的交互的过程中,遇见数据传输时同事和我说用…...
Mendelson AS2 介绍下载和配置
最近与一家国外公司做EDI对接,并且EDI通讯工具是基于AS2协议的。目前开源的as2的开源项目有openas2,Mendelson AS2,和国人写的freeas2但是,现在freeas2已经被从开源中国不能下载了,变为收费的版本了。 如果你需要使用基于AS2协议…...
旅游海报图怎么做二维码展示?扫码即可查看图片
现在旅游攻略的海报可以做成二维码印刷在宣传单单页或者分享给用户来了解目的地的实际情况,出行路线、宣传海报等。用户只需要扫描二维码就可以查看内容,更加的方便省劲,那么旅游海报的图片二维码制作的技巧有哪些呢?使用图片二维…...
常用git指令
初始化Git仓库:git init 添加文件到暂存区:git add <file> 提交更改到本地仓库:git commit -m "commit message" 查看本地仓库的提交历史:git log 创建分支:git branch <branch_name> 切换分支:git checkout <branch_name> 查看所有分支:git…...
【FPGA】分享一些FPGA协同MATLAB开发的书籍
在做FPGA工程师的这些年,买过好多书,也看过好多书,分享一下。 后续会慢慢的补充书评。 【FPGA】分享一些FPGA入门学习的书籍【FPGA】分享一些FPGA协同MATLAB开发的书籍 【FPGA】分享一些FPGA视频图像处理相关的书籍 【FPGA】分享一些FPGA高速…...
幺模矩阵-线性规划的整数解特性
百度百科:幺模矩阵 在线性规划问题中,如果A为幺模矩阵,那么该问题具有最优整数解特性。也就是说使用单纯形法进行求解,得到的解即为整数解。无需再特定使用整数规划方法。 m i n c T x s . t . { A x ≥ b x ≥ 0 \begin{align*} min \quad…...
数据分析思维
Why&What 数据分析是为了驱动决策赋能业务。在数据分析过程中需要对目标进行拆解量化,如何拆解量化目标便是数据分析思维。 在任务拆解过程中使用的软件、统计模型、分析方法等为分析工具和手段,如何在恰当的场景合理的使用这些工具、模型、方法、手…...
C++ boost planner_cond_.wait(lock) 报错1225
1.如下程序段 boost unique_lock doesn’t own the mutex: Operation not permitted 问题: 其中makePlan是一个线程。这里的unlock导致错误这个报错 boost unique_lock doesn’t own the mutex: Operation not permitted bool navigation::makePlan(){ //cv::named…...
LeetCode刷题--- 字母大小写全排列
个人主页:元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 http://t.csdnimg.cn/hKh2l 前言:这个专栏主要讲述递归递归、搜索与回…...
165. 小猫爬山(DFS之剪枝与优化)
165. 小猫爬山 - AcWing题库 翰翰和达达饲养了 N 只小猫,这天,小猫们要去爬山。 经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 翰翰和达达只好花钱让它们…...
【Linux系统基础】(6)在Linux上大数据NoSQL数据库HBase集群部署、分布式内存计算Spark环境及Flink环境部署详细教程
大数据NoSQL数据库HBase集群部署 简介 HBase 是一种分布式、可扩展、支持海量数据存储的 NoSQL 数据库。 和Redis一样,HBase是一款KeyValue型存储的数据库。 不过和Redis设计方向不同 Redis设计为少量数据,超快检索HBase设计为海量数据,…...
多维时序 | MATLAB实CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测
多维时序 | MATLAB实现CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测 目录 多维时序 | MATLAB实现CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测预测效果基本介…...
vs快捷键
ctrlMo 折叠代码块 ctrlML 打开代码块...
linux 内核时间计量方法
定时器中断由系统定时硬件以规律地间隔产生; 这个间隔在启动时由内核根据 HZ 值来编 程, HZ 是一个体系依赖的值, 在 <linux/param.h>中定义或者它所包含的一个子平台文 件中. 在发布的内核源码中的缺省值在真实硬件上从 50 到 1200 嘀哒每秒, 在软件模拟 器中往下到 24.…...
循环神经网络中的梯度消失或梯度爆炸问题产生原因分析(二)
上一篇中讨论了一般性的原则,这里我们具体讨论通过时间反向传播(backpropagation through time,BPTT)的细节。我们将展示目标函数对于所有模型参数的梯度计算方法。 出于简单的目的,我们以一个没有偏置参数的循环神经…...
JWT signature does not match locally computed signature
1. 问题背景 最近在协助团队小盆友调试一个验签问题,结果还“节外生枝”了,原来不是签名过程的问题,是token的问题。 当你看到“JWT signature does not match locally computed signature. JWT validity cannot be asserted and should not…...