题目名称 930. [河南省队2012] 找第k小的数
输入输出 kth.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2012-07-17
开放分组 全部用户
提交状态
分类标签
通过:199, 提交:849, 通过率:23.44%
Gravatar真的菜 100 0.475 s C++
GravatarGo灬Fire 100 0.480 s C++
GravatarGo灬Fire 100 0.518 s C++
GravatarCirno 100 0.537 s C++
GravatarGo灬Fire 100 0.551 s C++
GravatarHzoi_Hugh 100 0.558 s C++
Gravatarxyz117 100 0.599 s C++
GravatarAAAAAAAAAA 100 0.611 s C++
GravatarGo灬Fire 100 0.612 s C++
GravatarWildRage 100 0.662 s C++
关于 找第k小的数 的讨论
hzoi——占领此题(除了rank1)
GravatarOI永别
2014-05-04 20:13 1楼
Gravatarnew ioer
2015-04-05 19:50 2楼
同是hz
Gravatar0
2015-03-03 15:12 3楼
咱cdq只能在无优化开关下过…
Gravatar水中音
2015-03-28 08:15 4楼
原来整体二分是这么写的,学习了。
GravatarHouJikan
2015-03-31 20:06 5楼
这就是整体二分ORZ
Gravatarsvideo
2016-03-08 20:20 6楼
COGS的难度标签真不科学,这题题面基本和1534一样,而且这题的数据凶残地卡掉了快速选取。。然而快速选取就能过的1534却有两星
Gravatarliu_runda
2016-03-18 14:15 7楼
0.0
Gravatarztx
2016-06-14 20:11 8楼
回复 @♔ saber :
QAQ
GravatarSOBER GOOD BOY
2016-06-14 20:26 9楼
指针好慢。。。
Gravatarliu_runda
2016-07-14 17:30 10楼
作死非要挑战用快速选择,结果果然T5个
Gravatar_Itachi
2016-07-14 17:49 11楼
GravatarAntiLeaf
2017-05-25 16:02 12楼
Gravatar天一阁
2016-07-14 20:40 13楼
回复 @叶子の宿敌 :
刘润达教的,他说快速选择一点都不快~~,同时,神犇和我都认为,这和快速排序原理相似,所以叫他快速选择一点错也没有.
Gravatar_Itachi
2016-07-14 21:16 14楼
lower_bound()... 挺有用的哈
Gravatar洛克索耶夫
2016-07-14 21:41 15楼
回复 @独孤求败五剑界-利软重木无 :
这是我之前不知道从什么地方看到的QAQ,只是叫着方便并不知道这名字对不对啊QAQ
Gravatarliu_runda
2016-07-15 09:43 16楼
GravatarAntiLeaf
2017-05-25 16:02 17楼
水了一波主席树。。。BTW: "数组太大不要开栈里面而应该用动态内存分配" * 3
Gravatarsxysxy
2016-07-20 21:21 18楼
GravatarAntiLeaf
2017-05-25 16:10 19楼
主席树写爆N次后
闲来无事重写一遍
这就A了
吓死宝宝了= =
————————————————————————————
顺便一提不要学我这种不写离散化直接暴力开主席树的家伙
GravatarAntiLeaf
2016-09-03 22:11 20楼
树套树被卡了QAQ这不科学
GravatarAntiLeaf
2016-09-18 15:40 21楼
这..pb_ds T得好惨...还是我打开方式不对?
Gravatarsxysxy
2016-09-28 12:34 22楼
好久没打主席树了,,复习一下。。。20倍空间,数据离散化....
Gravatarsxysxy
2016-10-26 19:55 23楼
淦,,,树状数组套权值线段树+离散化都被卡内存了....
Gravatarsxysxy
2016-12-20 09:19 24楼
模板
GravatarNew World
2017-01-15 19:23 25楼
GravatarGo灬Fire
2017-02-14 08:56 26楼
刚开始交的时候空间开小了。。。
GravatarHeHe
2017-03-10 09:54 27楼
终于把主席树查询第k小的方法自己脑补出来了2333
GravatarkZime
2017-05-31 11:02 28楼
二分真奇妙
GravatarJustWB
2017-07-03 15:51 29楼
可持久化Trie树解决此题,为什么榜上的那么快啊。。。
GravatarWildRage
2017-08-02 20:20 30楼
Gravatarxyz117
2017-09-30 10:21 31楼
GravatarHzoi_Mafia
2017-09-30 10:43 32楼
表示1534数据太水了。。。
此题死T啊啊啊啊。。。
Gravatar~玖湫~
2017-09-30 11:36 33楼
MDZZ,交错程序了。。。。
GravatarHzoi_QTY
2017-09-30 17:52 34楼
暑假的坑国庆填qwq
开心1a
GravatarHyoi_Turkey
2017-10-07 16:00 35楼
换个漂亮的代码,
和更优秀些的离散化。
GravatarFisher.
2017-10-10 10:18 36楼
主席树第二题。+离散化
GravatarShirry
2018-01-01 18:16 37楼
所以这道题离散化的意义是什么
Gravatarhyghb
2018-01-07 10:11 38楼
Gravatarwangxh
2019-08-07 11:31 39楼

930. [河南省队2012] 找第k小的数

★★★   输入文件:kth.in   输出文件:kth.out   简单对比
时间限制:1 s   内存限制:256 MB

题目描述

看到很短的题目会让人心情愉悦,所以给出一个长度为N的序列A1,A2,A3,...,AN,

现在有M个询问,每个询问都是Ai...Aj中第k小的数等于多少。


输入格式

第一行两个正整数N,M。
第二行N个数,表示序列A1,A2,...,AN。
紧着的M行,每行三个正整数i,j,k(k≤j-i+1),表示

询问Ai...Aj中第k小的数等于多少。


输出格式

共输出M行,第i行输出第i个询问的答案。


样例输入1:

4 3

4 1 2 3

1 3 1

2 4 3

1 4 4


样例输出1:
1
3
4

样例输入2:
5 5
4 2 9 9 10
1 3 1
2 4 3
1 4 4
3 5 2
2 5 2

样例输出2:
2
9
9
9
9

注释:
询问区间的第k小值并非严格第k小,例如样例2中第4个询问,询问3到5中第2小的数,
答案输出9,并不是严格第2小的10。

数据范围:
在50%的数据中,1<=N<=10000,1<=M<=10000,A[i]<=100000;
在100%的数据中,1<=N<=100000,1<=M<=100000,A[i]<=1000000;