255. 第K小数 (可持久化线段树,模板题,离散化,* * )

2024-04-28 01:52

本文主要是介绍255. 第K小数 (可持久化线段树,模板题,离散化,* * ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

255. 第K小数 - AcWing题库

给定长度为 N 的整数序列 A,下标为 1∼N。

现在要执行 M 次操作,其中第 i 次操作为给出三个整数 li,ri,ki,求 A[li],A[li+1],…,A[ri] (即 A 的下标区间 [li,ri])中第 ki 小的数是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数,表示整数序列 A。

接下来 M 行,每行包含三个整数 li,ri,ki,用以描述第 i 次操作。

输出格式

对于每次操作输出一个结果,表示在该次操作中,第 k 小的数的数值。

每个结果占一行。

数据范围

N≤105,M≤104,|A[i]|≤109

输入样例:
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
输出样例:
5
6
3

解析: 

本题离散化后,线段树的节点保存的是某个值域区间和区间内的数的个数,思路参考D 无限的韵律源点 (STL_set +对顶堆 , 线段树+离散化 , * * * * *)-CSDN博客的线段树做法

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f;
const LL Mod = 2147483648;
const int N = 1e5 + 10, M = N * 25;
int n, m;
int a[N];
vector<int>num;
struct Node {int l, r;int cnt;
}tr[N*4+N*17];
int root[N],idx;int find(int x) {return lower_bound(num.begin(), num.end(), x) - num.begin();
}int build(int l, int r) {int p = ++idx;if (l == r)return p;int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);return p;
}int insert(int p, int l, int r, int x) {int q = ++idx;tr[q] = tr[p];if (l == r) {tr[q].cnt++;return q;}int mid = l + r >> 1;if (x <= mid)tr[q].l = insert(tr[p].l, l, mid, x);else tr[q].r = insert(tr[p].r, mid + 1, r, x);tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;return q;
}int query(int p, int q, int l, int r, int k) {if (l == r) {return l;}int mid = l + r >> 1;int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);num.push_back(a[i]);}sort(num.begin(), num.end());num.erase(unique(num.begin(), num.end()), num.end());//cout << "__________++++++++++++++++++++++" << endl;root[0] = build(0, num.size() - 1);//cout << "____________________________" << endl;for (int i = 1; i <= n; i++) {root[i] = insert(root[i - 1], 0, num.size() - 1, find(a[i]));}//cout << "_____________________________" << endl;int l, r, x;while (m--) {scanf("%d%d%d", &l, &r, &x);printf("%d\n", num[query(root[l - 1], root[r], 0, num.size() - 1, x)]);}return 0;
}

这篇关于255. 第K小数 (可持久化线段树,模板题,离散化,* * )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>

Redis持久化机制之RDB与AOF的使用

《Redis持久化机制之RDB与AOF的使用》:本文主要介绍Redis持久化机制之RDB与AOF的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis持久化机制-RDB与AOF一、RDB持久化机制1、RDB简介2、RDB的工作原理3、RDB的优缺点4

Python中Flask模板的使用与高级技巧详解

《Python中Flask模板的使用与高级技巧详解》在Web开发中,直接将HTML代码写在Python文件中会导致诸多问题,Flask内置了Jinja2模板引擎,完美解决了这些问题,下面我们就来看看F... 目录一、模板渲染基础1.1 为什么需要模板引擎1.2 第一个模板渲染示例1.3 模板渲染原理二、模板

利用Python打造一个Excel记账模板

《利用Python打造一个Excel记账模板》这篇文章主要为大家详细介绍了如何使用Python打造一个超实用的Excel记账模板,可以帮助大家高效管理财务,迈向财富自由之路,感兴趣的小伙伴快跟随小编一... 目录设置预算百分比超支标红预警记账模板功能介绍基础记账预算管理可视化分析摸鱼时间理财法碎片时间利用财

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

SpringCloud之consul服务注册与发现、配置管理、配置持久化方式

《SpringCloud之consul服务注册与发现、配置管理、配置持久化方式》:本文主要介绍SpringCloud之consul服务注册与发现、配置管理、配置持久化方式,具有很好的参考价值,希望... 目录前言一、consul是什么?二、安装运行consul三、使用1、服务发现2、配置管理四、数据持久化总

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

Redis事务与数据持久化方式

《Redis事务与数据持久化方式》该文档主要介绍了Redis事务和持久化机制,事务通过将多个命令打包执行,而持久化则通过快照(RDB)和追加式文件(AOF)两种方式将内存数据保存到磁盘,以防止数据丢失... 目录一、Redis 事务1.1 事务本质1.2 数据库事务与redis事务1.2.1 数据库事务1.