【第K小数——可持久化权值线段树】

ops/2025/3/18 14:46:56/

题目

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int a[N], b[N];
int n, m, len;
int rt[N], idx; // idx 是点分配器struct node
{int l, r;int s;
} tr[N * 22];int getw(int x)
{return lower_bound(b + 1, b + len + 1, x) - b;
}int build(int l, int r)
{int p = ++idx;tr[p].s = 0; // 初始化 sif (l < r){int mid = l + r >> 1;tr[p].l = build(l, mid);tr[p].r = build(mid + 1, r);}return p;
}int insert(int x, int l, int r, int v)
{int p = ++idx;tr[p] = tr[x];tr[p].s++; // 更新 sif (l < r){int mid = l + r >> 1;if (v <= mid) tr[p].l = insert(tr[x].l, l, mid, v);else tr[p].r = insert(tr[x].r, mid + 1, r, v);}return p;
}int query(int x, int y, int l, int r, int k)
{if (l == r) return l;int mid = l + r >> 1;int s = tr[tr[x].l].s - tr[tr[y].l].s; // 左子树的节点数if (k <= s) return query(tr[x].l, tr[y].l, l, mid, k);else return query(tr[x].r, tr[y].r, mid + 1, r, k - s);
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &a[i]), b[i] = a[i];sort(b + 1, b + n + 1);len = unique(b + 1, b + n + 1) - b - 1; // 初始化全局变量 lenrt[0] = build(1, len); // 使用 len 作为区间范围for (int i = 1; i <= n; i++)rt[i] = insert(rt[i - 1], 1, len, getw(a[i])); // 更新 rt[i]while (m--){int l, r, k;scanf("%d%d%d", &l, &r, &k);printf("%d\n", b[query(rt[r], rt[l - 1], 1, len, k)]); // 映射回 b,相对大小(位置)映射回实际大小}return 0;
}


http://www.ppmy.cn/ops/166788.html

相关文章

Word 小黑第22套

对应大猫23 续编号&#xff08;编号断了&#xff0c;从一开始&#xff09;&#xff1a;点编号&#xff0c;再设置编号值 插入以图标方式显示的文档&#xff1a;插入 -对象 -由文件创建 &#xff08;这里要链接到文件也要勾选 不然扣一分&#xff09; 一个页面设为横向不影响上…

探索具身多模态大模型:开发、数据集和未来方向(下)

25年2月来自广东人工智能和数字经济实验室、深圳大学、巴黎理工学院和巴黎高等师范学院、中山大学的论文“Exploring Embodied Multimodal Large Models: Development, Datasets, and Future Directions”。 近年来&#xff0c;具身多模态大模型 (EMLM) 因其在复杂的现实环境中…

关于Redis的集群(上)

目录 基本概念 数据分片算法 哈希求余 ​编辑一致性哈希算法 哈希槽分区算法 搭建集群环境 创建目录和配置 编写 docker-compose.yml 启动容器 构建集群 基本概念 广义的集群&#xff0c;只要是多个机器构成了分布式系统&#xff0c;都可以成为是一个“集群”。 但…

Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实战指南

Spring Boot拦截器&#xff08;Interceptor&#xff09;与过滤器&#xff08;Filter&#xff09;深度解析&#xff1a;区别、实现与实战指南 一、核心概念对比 1. 本质区别 维度过滤器&#xff08;Filter&#xff09;拦截器&#xff08;Interceptor&#xff09;规范层级Serv…

SpringBoot美发门店管理系统开发与设计

在幽络源&#xff0c;我们致力于为开发者提供优质的技术资源和项目源码。今天&#xff0c;我们为大家分享一款基于SpringBoot开发的美发门店管理系统。该系统功能全面&#xff0c;操作便捷&#xff0c;适合中小型美发门店的管理需求。以下是系统的详细介绍。 系统功能模块 1.…

C++进阶——map和set的使用

目录 1、序列式容器和关联式容器 2、set系列的使用 2.1 set和multiset的参考文档 2.2 set类的介绍 2.3 set的构造和迭代器 2.4 set的增删查 2.5 set的insert和迭代器遍历 2.6 set的find和erase 2.7 set的lower_bound和upper_bound 2.8 multiset和set的差异 2.9 349.…

spring启动流程

Spring启动流程 随着springboot的功能越来越强大&#xff0c;我们逐渐忘记了spring&#xff0c;但是每当遇到问题时缺无从下手&#xff0c; 我们在享受springboot给我们带来的便利的同时更应该了解其底层原理&#xff0c;知其然更要知其所以然&#xff0c;下面我们一起进入spr…

SSH反向隧道

SSH反向隧道是一种通过SSH协议将内网服务暴露到公网的技术&#xff0c;尤其适用于内网主机没有公网IP的情况。以下是详细的讲解&#xff1a; 1. 基本概念 反向隧道&#xff08;Reverse Tunnel&#xff09;&#xff1a;与传统SSH隧道&#xff08;内网主机作为客户端连接外网&a…