P3834 【模板】可持久化线段树 1(主席树)

    • 2K通过
    • 4.7K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 主席树 可持久化 离散化 线段树
  • 难度 提高+/省选-
  • 时空限制 1000ms-1200ms / 128MB-256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    这是个非常经典的主席树入门题——静态区间第K小

    数据已经过加强,请使用主席树。同时请注意常数优化

    题目描述

    如题,给定N个正整数构成的序列,将对于指定的闭区间查询其区间内的第K小值。

    输入输出格式

    输入格式:

    第一行包含两个正整数N、M,分别表示序列的长度和查询的个数。

    第二行包含N个正整数,表示这个序列各项的数字。

    接下来M行每行包含三个整数 $ l, r, k$ , 表示查询区间 $[l, r]$ 内的第k小值。

    输出格式:

    输出包含k行,每行1个正整数,依次表示每一次查询的结果

    输入输出样例

    输入样例#1: 复制
    5 5
    25957 6405 15770 26287 26465 
    2 2 1
    3 4 1
    4 5 1
    1 2 2
    4 4 1
    输出样例#1: 复制
    6405
    15770
    26287
    25957
    26287
    

    说明

    数据范围

    对于20%的数据满足: $1 \leq N, M \leq 10$

    对于50%的数据满足: $1 \leq N, M \leq 10^3$

    对于80%的数据满足: $1 \leq N, M \leq 10^5$

    对于100%的数据满足: $1 \leq N, M \leq 2\cdot 10^5$

    对于数列中的所有数 $a_i$ ,均满足 $-{10}^9 \leq a_i \leq {10}^9$

    样例数据说明

    N=5,数列长度为5,数列从第一项开始依次为 $[25957, 6405, 15770, 26287, 26465 ]$

    第一次查询为 $[2, 2]$ 区间内的第一小值,即为6405

    第二次查询为 $[3, 4]$ 区间内的第一小值,即为15770

    第三次查询为 $[4, 5]$ 区间内的第一小值,即为26287

    第四次查询为 $[1, 2]$ 区间内的第二小值,即为25957

    第五次查询为 $[4, 4]$ 区间内的第一小值,即为26287

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。