SDUTOJ 3043 迷之容器 线段树求全局第k小

2024-08-24 23:08

本文主要是介绍SDUTOJ 3043 迷之容器 线段树求全局第k小,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

迷之容器

Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^

题目描述

FF最近得到了一个神奇的容器。他可以不停地往这个容器里放入数字,如果刚放入的这个数字已存在于容器中,那么容器只会保留其中的一个。

现在FF又有了一个很蛋疼的想法,他在放入了若干个数字之后,想知道容器中第K小的数字是多少。

 

 

输入

 多组输入。

对于每组数据,初始时容器为空。

每组数据输入一个n(1 <= n <= 100000),代表有n次查询和放入操作。

接下来的n行,每行一个字符 c和数字x (-1000,000,000<= x <= 1000,000,000),用空格隔开。

c “ P ”,则表明FF要放入x,此时[-1000 000 000,1000 000 000]

 “Q”,则表明FF想知道容器中第x小的数是多少,若不存在则用 -1代表,此时x[1100000]

输出

 对于每次询问,输出一个数字代表答案。

示例输入

4
P 1
Q 1
P -1
Q 2

示例输出

1
1

提示

 

来源

 zmx


假期刷数据结构线段树的时候真的没遇到这种问题——线段树求第K小(大),今天留下(水题)模板一份:



#include <stdio.h>
#include <string.h>
#include <algorithm>
#define ll long longusing namespace std;struct Node
{ll num;int op;
}blf[100010];//存储操作的数组ll sr[100010],lsh[100010];//要输入的数
int d[100010 << 2];//线段树数组,维护有多少数存在
int ans;//答案记录int b_sch(int l,int r,ll key)//二分查找,找要添加的数离散化后(下标)编号是多少
{while(l <= r){int mid = (l + r) >> 1;if(key == lsh[mid])return mid;else if(key > lsh[mid])l = mid + 1;elser = mid - 1;}return -1;
}void up(int step)//回溯函数
{d[step] = d[step << 1] + d[step << 1 | 1];
}
void upd(int s,int t,int uu,int unum,int step)//线段树更新,就是把数设为存在
{if(s >= t){d[step] = unum;return ;}int mid = (s + t) >> 1;if(uu <= mid)upd(s,mid,uu,unum,step << 1);if(uu > mid)upd(mid + 1,t,uu,unum,step << 1 | 1);up(step);
}void qu(int s,int t,ll qq,int step)//线段树询问
{if(s >= t)//如果找到了某个节点{ans = s;//标记他所代表的数的编号return ;}if(t - s > 0)//如果没到最终节点{int mid = (s + t) >> 1;if(qq <= (ll)(d[step << 1]))//如果要找的这个数比左子树上的数小  就必然在左子树qu(s,mid,qq,step << 1);elsequ(mid + 1,t,qq - (ll)(d[step << 1]),step << 1 | 1);//不在左子树,必在右子树,但查找的//第qq(k)小要减去左子树的数的个数才能继续查找}
}int main()
{int n;char str[10];while(~scanf("%d",&n)){int cnt1 = 0,cnt2 = 0;for(int i = 0;i < n;i++){scanf("%s%lld",str,&blf[i].num);if(str[0] == 'P'){blf[i].op = 1;sr[cnt1++] = blf[i].num;}else{blf[i].op = 2;//1代表P   2代表 Q}}sort(sr,sr + cnt1);//排序lsh[++cnt2] = sr[0];for(int i = 1;i < cnt1;i++){if(lsh[cnt2] != sr[i]){lsh[++cnt2] = sr[i];}}//离散化memset(d,0,sizeof(d));//初始化线段树for(int i = 0;i < n;i++){if(blf[i].op == 1){int fh = b_sch(1,cnt2,blf[i].num);//上面有介绍upd(1,cnt2,fh,1,1);//更新}else{if((ll)(d[1]) < blf[i].num){printf("-1\n");//如果已有的数比要查找的k小的话 就不存在}else{ans = 0;qu(1,cnt2,blf[i].num,1);//    printf("ans = %d\n",ans);printf("%lld\n",lsh[ans]);}}}}return 0;
}






这篇关于SDUTOJ 3043 迷之容器 线段树求全局第k小的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103866

相关文章

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》:本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整(可选)重新构建和运行总结Tomcat容器替

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

grom设置全局日志实现执行并打印sql语句

《grom设置全局日志实现执行并打印sql语句》本文主要介绍了grom设置全局日志实现执行并打印sql语句,包括设置日志级别、实现自定义Logger接口以及如何使用GORM的默认logger,通过这些... 目录gorm中的自定义日志gorm中日志的其他操作日志级别Debug自定义 Loggergorm中的

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

springboot日期格式化全局LocalDateTime详解

《springboot日期格式化全局LocalDateTime详解》文章主要分析了SpringBoot中ObjectMapper对象的序列化和反序列化过程,并具体探讨了日期格式化问题,通过分析Spri... 目录分析ObjectMapper与jsonSerializer结论自定义日期格式(全局)扩展利用配置

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in