#P3834. 【模板】可持久化线段树 2

    ID: 4571 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>线段树离散化O2优化主席树可持久化

【模板】可持久化线段树 2

题目背景

这是个非常经典的可持久化权值线段树入门题——静态区间第 kk 小。

数据已经过加强,请使用可持久化权值线段树。同时请注意常数优化

题目描述

如题,给定 nn 个整数构成的序列 aa,将对于指定的闭区间 [l,r][l, r] 查询其区间内的第 kk 小值。

输入格式

第一行包含两个整数,分别表示序列的长度 nn 和查询的个数 mm
第二行包含 nn 个整数,第 ii 个整数表示序列的第 ii 个元素 aia_i
接下来 mm 行每行包含三个整数 l,r,k l, r, k , 表示查询区间 [l,r][l, r] 内的第 kk 小值。

输出格式

对于每次询问,输出一行一个整数表示答案。

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

6405
15770
26287
25957
26287

提示

样例 1 解释

n=5n=5,数列长度为 55,数列从第一项开始依次为{25957,6405,15770,26287,26465}\{25957, 6405, 15770, 26287, 26465\}

  • 第一次查询为 [2,2][2, 2] 区间内的第一小值,即为 64056405
  • 第二次查询为 [3,4][3, 4] 区间内的第一小值,即为 1577015770
  • 第三次查询为 [4,5][4, 5] 区间内的第一小值,即为 2628726287
  • 第四次查询为 [1,2][1, 2] 区间内的第二小值,即为 2595725957
  • 第五次查询为 [4,4][4, 4] 区间内的第一小值,即为 2628726287

数据规模与约定

  • 对于 20%20\% 的数据,满足 1n,m101 \leq n,m \leq 10
  • 对于 50%50\% 的数据,满足 1n,m1031 \leq n,m \leq 10^3
  • 对于 80%80\% 的数据,满足 1n,m1051 \leq n,m \leq 10^5
  • 对于 100%100\% 的数据,满足 1n,m2×1051 \leq n,m \leq 2\times 10^5ai109|a_i| \leq 10^91lrn1 \leq l \leq r \leq n1krl+11 \leq k \leq r - l + 1