【第K小数——可持久化权值线段树】
题目
代码
#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;
}相关文章：
【第K小数——可持久化权值线段树】
题目 代码 #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 bui…...
需要使用新应用以打开此ms-gamingoverlay链接怎么解决
要解决Windows系统提示“需要使用新应用以打开此ms-gamingoverlay链接”的问题，通常与系统自带的游戏工具栏（Game Bar）或Xbox相关应用缺失或配置错误有关。以下是综合多个来源的详细解决方法： 方法1：关闭游戏栏功能 这…...
五子棋小游戏-简单开发版
一、需求分析 开发一个基于 Pygame 库的五子棋小游戏，允许两名玩家在棋盘上轮流落子，当有一方达成五子连珠时游戏结束，显示获胜信息，并提供退出游戏和重新开始游戏的操作选项。 1.棋盘显示 ： 显示一个 15x15 的五子棋…...
C语言内存函数讲解
（一）memcpy函数 这是memcpy函数的说明。它的头文件是string.h。函数原型是 void* memcpy(void* destination, const void* source, size_t num) 第一个参数是一个指向一个字符串的指针，第二个也是一样的。而第三个参数是复制的字节个数。这…...
2018年全国职业院校技能大赛高职组-计算机网络应用竞赛竞赛样题C卷
目录 总体规划 模块二：设备基础信息配置 模块三：网络搭建与网络冗余备份方案部署 模块四：移动互联网搭建与网优 模块五：出口安全防护与远程接入 总体规划 CII教育公司在进行企业大学信息化建设的过程中，为了保证北京校区、广州校区与本部校区的日常OA办公通信等关键业务，…...
《解锁Flutter：跨平台开发的未来之光》：此文为AI自动生成
《解锁Flutter：跨平台开发的未来之光》：此文为AI自动生成 Flutter：崭新时代的跨平台框架 在当今数字化浪潮中，移动应用已成为人们生活中不可或缺的一部分。无论是购物、社交、娱乐还是办公，我们都离不开各种手机应用…...
基于大数据的酒类商品数据可视化分析系统
【大数据】基于大数据的酒类商品数据可视化分析系统 （完整系统源码开发笔记详细部署教程）✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统充分利用Python与Flask的强大后端处理能力，结合前端Layui框架࿰…...
中的性质)
【数学建模】一致矩阵的应用及其在层次分析法(AHP)中的性质
一致矩阵在层次分析法(AHP)中的应用与性质 在层次分析法(AHP)中，一致矩阵是判断矩阵的一种理想状态，它反映了决策者判断的完全合理性和一致性，也就是为了避免决策者认为“A比B重要，B比C重要，但是C又比A重要”的矛盾。…...
【YOLOv8】YOLOv8改进系列（7）----替换主干网络之LSKNet
主页：HABUO🍁主页：HABUO 🍁YOLOv8入门改进专栏🍁 🍁如果再也不能见到你，祝你早安，午安，晚安🍁 【YOLOv8改进系列】： 【YOLOv8】YOLOv8结构解读…...
【MySQL】多表查询（笛卡尔积现象，联合查询、内连接、左外连接、右外连接、子查询）-通过练习快速掌握法
在DQL的基础查询中，我们已经学过了多表查询的一种：联合查询（union）。本文我们将系统的讲解多表查询。 笛卡尔积现象 首先，我们想要查询emp表和stu表两个表，按照我们之前的知识栈，我们直接使用…...
练习-平方拆分问题（线性筛法-筛质数）
问题描述 小蓝非常热爱数学，一天老师给小蓝出了一道数学题，想锻炼锻炼小蓝的思维能力。题目是这样的：给定两个数 a 和 b，在 a 到 b（包括 a,b）之间所有数的平方当中，试问有几个数能够表示为 xy …...
)
CVE-2018-2628(使用 docker 搭建)
介绍： 是一个影响 Oracle WebLogic Server 的严重漏洞，属于 远程代码执行（RCE） 漏洞。以下是对该漏洞的详细分析： ● 漏洞类型: 远程代码执行(RCE) ● 影响范围:Oracle WebLogic Server 10.3.6.0, 12.1.3.0, 12.2.1.2…...
【深度学习与大模型基础】第5章-线性相关与生成子空间
线性相关是指一组向量中，至少有一个向量可以表示为其他向量的线性组合。具体来说，对于向量组 v1,v2,…,vn，如果存在不全为零的标量 c1,c2,…,cn使得： c1v1c2v2…cnvn0 则称这些向量线性相关。否则，它们线性无关。 举…...
使用 PaddlePaddle 官方提供的 Docker 镜像
CUDA版本高PaddlePaddle不支持时，可以使用 PaddlePaddle 官方提供的 Docker 镜像 1. 安装 Docker Desktop1.1 下载 Docker Desktop1.2 安装 Docker Desktop1.3 启用 WSL 2 或 Hyper-V1.4 启动 Docker Desktop1.5 Docker不运行解决方法 2. 拉取 PaddlePaddle Docker …...
LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS 论文阅读
一、TL；DR 为什么要这么做？预训练模型越来越大，比如GPT-3 175B训练独立变得越来越不可行方法：冻结预训练模型的权重，在Transformer架构的每一层中注入可训练的低秩分解矩阵效果：训练参数量减少10000x&…...
企业的应用系统
一、人力资源系统 负责管理员工信息，处理入职，离职，调岗。 1、一般员工的信息有电子档和纸质档两份。 电子档经常是excel文件。 2、高级的公司会建立一套Web应用系统。 3、实现的功能： 新员工入职登记 (登记信息一般是：…...
SpringBoot手动注册定时任务
一、背景 项目存在这样一个场景。程序启动过程中，在Spring的Bean组件注册完毕后，会初始化一些基础数据到数据库中，而项目中有部分定时任务需要依赖这些基础数据才能正常运行。如果直接使用Scheduled注解标注定时任务方法，会导致定…...
通过 Python 爬虫提高股票选股胜率
此贴为Python爬虫技术学习贴 在股票中，即便有了选股规则，从5000多只股票中筛选出符合规则的股票也是十分困难的，于是想通过爬虫来实现自动化的快速选股。全文用GP代替股票 实现方案 1、指定两套规则，第一套弱约束，第…...
)
InternVL：论文阅读 -- 多模态大模型(视觉语言模型)
更多内容：XiaoJ的知识星球 文章目录 InternVL: 扩展视觉基础模型与通用视觉语言任务对齐1.概述2.InternVL整体架构1）大型视觉编码器：InternViT-6B2）语言中间件：QLLaMA。3）训练策略（1）…...
代码随想录算法训练营第三十五天（20250303） |01背包问题 二维，01背包问题 一维，416. 分割等和子集 -[补卡20250316]
01背包问题 二维 链接 遍历物品没有大小顺序要求重点是模拟，推导出递推公式 #include <iostream> #include <vector>int main(){int m, n;std::cin>>m>>n;std::vector<int> weight(m,0),value(m,0);for(int i{0}; i<m; i){std:…...
RGV调度算法（三）--遗传算法
1、基于时间窗 https://wenku.baidu.com/view/470e9fd8b4360b4c2e3f5727a5e9856a57122693.html?_wkts_1741880736197&bdQuery%E7%8E%AF%E7%A9%BF%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95 2.2019年MathorCup高校数学建模挑战赛B题 2019-mathorcupB题-环形穿梭机调度模型&a…...
并发编程-
一、简述 线程：线程是cpu可执行的最小单位，而进程是操作系统可分配的最小资源单位。一个进程中可以有多个线程。 线程的五个状态： 新建（new Thread()） 就绪 （thread.start()） 运行（…...
Mac中nvm切换node版本失败，关闭终端再次打开还是之前的node
Mac中使用 nvm 管理 node 版本，在使用指令：nvm use XXX 切换版本之后。 关闭终端，再次打开，输入 node -v 还是得到之前的 node 版本。 原因： 在这里这个 default 中有个 node 的版本号，使用 nvm use 时&a…...
C语言（25）
一.数据在内存中的存储 1.整数在内存中的存储 整数在内存中以二进制的形式储存，分别为原码，补码，反码 有符号的整数，在上述三种形式都有符号位和数值位两个部分，符号位为0是正数，1是负数，最高…...
HTML、CSS
什么是HTML、CSS HTML结构标签及特点 CSS引入方式 CSS颜色表示形式： CSS引入方式、颜色表示、颜色属性 CSS选择器 超链接...
c#:主窗体与子控件之间的数据传递：基于事件和委托的实现
1. 概述 在WPF中，主窗体与子控件之间的数据传递通常通过以下两种方式实现： 事件（Event）：主窗体触发事件，子控件订阅事件并接收数据。 委托（Delegate）：通过委托将子控件…...
Dynamics 365 启用用户安全角色变更的审核功能
D365自身的审核功能这里就不说了，是一个很古老的功能，用过D365的人应该都知道，今天要说的是用户安全角色变更的审核记录。 很多人用系统的审核功能，更多的是用来追踪用户的登录记录，或者记录的修改记录。 而实际的项目…...
MyBatis注解
MyBatis 的注解（Annotations）提供了一种简洁的方式来配置 SQL 映射，而无需使用 XML 文件。通过在 Mapper 接口的方法上使用注解，可以直接在 Java 代码中定义 SQL 语句和相关映射。这种方式使得代码更加集中和易于维护，…...
1.Windows+vscode+cline+MCP配置
文章目录 1.简介与资源2.在windows中安装vscode及Cline插件1. 安装vscode2. 安装Cline插件3. 配置大语言模型3. 配置MCP步骤(windows) 1.简介与资源 MCP官方开源仓库 MCP合集网站 参考视频 2.在windows中安装vscode及Cline插件 1. 安装vscode 2. 安装Cline插件 Cline插件…...
94.HarmonyOS NEXT动画系统实现教程：深入理解FuncUtils
温馨提示：本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦！ HarmonyOS NEXT动画系统实现教程：深入理解FuncUtils 文章目录 HarmonyOS NEXT动画系统实现教程：深入理解FuncUtils1. 动画系…...
Python----数据分析（Pandas一：pandas库介绍，pandas操作文件读取和保存）
一、Pandas库 1.1、概念 Pandas是一个开源的、用于数据处理和分析的Python库，特别适合处理表格类数 据。它建立在NumPy数组之上，提供了高效的数据结构和数据分析工具，使得数据操作变得更加简单、便捷和高效。 Pandas 的目标是成为 Python 数据…...
设计模式之原型模式：原理、实现与应用
引言 原型模式（Prototype Pattern）是一种创建型设计模式，它通过复制现有对象来创建新对象，而不是通过实例化类。原型模式特别适用于创建成本较高的对象，或者需要动态配置的对象。本文将深入探讨原型模式的原理、实现方…...
平方矩阵问题
Ⅰ 回字形二维数组 #include <iostream> #include <iomanip> using namespace std; int main(){int n;while(cin>>n,n){for(int i0; i<n;i){for(int j0; j<n; j){int upi, downn-i1, leftj, rightn-j1;cout<<min(min(up,down),min(left,right)…...
C语言之链表
文章目录 前言 一、链表基本概念 1、声明节点结构 2、创建节点变量 3、链表所有节点 4、遍历链表 二、add添加 三、insert插入 四、remove删除 五、查找 总结 前言 链表是一种重要的数据结构，用于存储和组织数据。它是由一系列节点组成的数据结构&#x…...
RabbitMQ延迟消息
文章目录 延迟消息死信交换机延迟消息延迟消息应用场景 延迟消息 生产者在发送消息的时候指定一个时间，消费者不会立即收到该消息，而是在指定时间之后才收到消息，这就是延迟消息。 比如说这么一个场景，用户下单后将商品库存进行…...
Unity中WolrdSpace下的UI展示在上层
一、问题描述 Unity 中 Canvas使用World Space布局的UI，想让它不被3d物体遮挡，始终显示在上层。 二、解决方案 使用shader解决 在 UI 的材质中禁用深度测试（ZTest），强制 UI 始终渲染在最上层。 Shader "Custo…...
【从零开始学习计算机科学】算法分析（一）算法、渐进分析、递归分析
【从零开始学习计算机科学】算法分析（一）算法、渐进分析、递归分析 算法算法分析正确性算法完成需要的时间使用的存储空间简单性渐进分析递归分析主方法求解递归式递归树求解代入法概率分析和随机算法顺序统计量算法 什么是算法？算法（Algorithm）是指解题方案的准确而完整…...
【菜鸟飞】Conda安装部署与vscode的结合使用
介绍 Conda 是一个跨平台的开源工具，用于管理软件包和环境。最初由 Anaconda 公司开发，它的设计目标是支持数据科学和机器学习领域，但其功能不仅局限于此。 以下是 Conda 的核心特点： 包管理：安装、更新、卸载各种库…...
LeetCode2593 标记所有元素后数组的分数
贪心算法实战：数组标记与分数计算（LeetCode 同类题解析） 一、问题描述 给定一个正整数数组 nums，按以下规则计算最终分数： 初始分数 score 0每次选择最小且未被标记的元素（值相同选下标最小）…...
【C++多线程】thread
C中的std::thread是C11引入的线程库的一部分，提供了创建和管理线程的能力。它封装了操作系统的线程接口，使得在C中更方便地进行多线程编程。 1. std::thread 的定义 std::thread 类位于<thread>头文件中，定义在std命名空间下ÿ…...
补充二分LIS
B3637 最长上升子序列 题目描述 这是一个简单的动规板子题。 给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。 最长上升子序列是指，从原序列中按顺序取出一些数字排…...
airtest用法
安装python3.7.9 64 python3 -m pip install -U airtest 或者： git clone https://github.com/AirtestProject/Airtest.git pip install -e airtest 下载adb 可以开始无界面的airtest 下载AirtestIDE 安装与启动 - Airtest Project Docs Airtest Project...
30天学习Java第四天——设计模式
设计模式概述 设计模式是一套被广泛接受的、经过试验的、可反复使用的基于面向对象的软件设计经验总结，它是开发人员在软件设计时，对常见问题的解决方案的总结和抽象。 一句话就是，设计模式是针对软件开发中常见问题和模式的通用解决方案。 …...
MongoDB 和 Elasticsearch的区别、优缺点对比，以及选型建议
MongoDB 和 Elasticsearch 在存储和搜索方面各有特点，适用于不同的场景。以下是它们的区别、优缺点对比，以及选型建议。 1. 概述 MongoDB：分布式 NoSQL 文档数据库，基于 BSON（类似 JSON）的文档存储&#x…...
在Android中，子线程可以更新UI吗
目录 为什么子线程不能直接更新UI？ 如何正确在子线程更新UI？ 1. 使用runOnUiThread方法 2. 通过Handler发送消息到主线程 3. 使用View.post(Runnable)方法 4. 结合AsyncTask（已过时，仅作了解） 5. 使用Kotlin协程…...
unittest vs pytest区别
unittest vs pytest 对比 unittest 像“手动挡汽车”：操作步骤多，规则严格，适合老司机。pytest 像“自动挡汽车”：开起来轻松，功能强大，适合新手和高效开发。 区别点unittest（你学过的&…...
OpenAI与谷歌DeepMind新品同日竞技，谁能引领机器人现实任务新潮流？
2025年3月12日，科技巨头谷歌DeepMind与OpenAI均发布了与机器人执行现实任务相关的新产品：谷歌DeepMind的新AI模型、OpenAI的Agents工具集，二者在技术路径、应用场景、安全机制设计等方面存在明显差异，其发展态势备受行业关注。 …...
JVM并发编程AQSsync锁ReentrantLock线程池ThreadLocal
并发编程2 synchronized锁实现**AQS****ReentrantLock实现****JUC 常用类**池的概念 ThreadLocalThreadLocal原理内存泄露强引用:软引用弱引用虚引用ThreadLocal内存泄露 synchronized锁实现 synchronized是一个关键字,实现同步,还需要我们提供一个同步锁对象,记录锁状态,记录…...
特殊 IP 地址
文章目录 特殊IP地址概述受限广播地址（Limited Broadcast Address）直接广播地址（Directed Broadcast Address）多播地址（Multicast Address）环回地址（Loopback Address）本网络本主机&…...
SSL/TLS 1.2过程：Client端如何验证服务端证书？
快速回顾非对称加密和对称加密 首先快速说一下非对称加密和对称加密。非对称加密，就是有一个公钥和私钥(成对存在)。 公钥对一段文本A加密得到文本B，只有对应的私钥能对B解密得到A。 私钥对一段文本C加密得到文本D，只有对应的公钥能对D解密得…...