题目描述

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

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

输入输出格式

输入格式:

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

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

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

输出格式:

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

输入输出样例

输入样例#1:

输出样例#1:

主席树入门题(反正我用树套树没水过去..)

就是可持久化线段树的权值线段树版本

对于每个节点是可减的

原序列1…n作为n个版本,一个一个插入进去,并生产新的版本

求kth的时候就像平衡树那样就行了

 


说点什么

avatar
  Subscribe  
提醒