logo AlgoBeat OnlineJudge
登录 注册

#103920. [BZOJ 3920] Yuuna的礼物

内存限制：512 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
上传者： 匿名
提交 提交记录 统计 测试数据 讨论 题解

题目描述

转眼就要到Karin的生日了！Yuuna她们想为她准备生日礼物！现在有许多礼物被排列成了一个一维序列，每个礼物都有一个价值。Yuuna对这个序列十分感兴趣。因此，你需要多次回答：在某个区间内出现次数第k1少的价值是多少，可能多个不同的价值出现次数均为第k1少，输出其中第k2小的，保证输入合法。注意内存限制。

例如：对于一个区间而言(当然不一定是有序的):

1,2,3,4,5,5,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12

权值出现次数

11出现次数第1少第1小

21第2小

31第3小

41第4小

52出现次数第2少第1小

62第2小

74出现次数第3少第1小

84第2小

94第3小

104第4小

116出现次数第4少第1小

1210出现次数第5少第1小

若k1=3，k2=2，代表询问这个区间里出现次数第3少的权值中第2小的，则应该输出8。

若k1=5，k2=1，代表询问这个区间里出现次数第5少的权值中第1小的，则应该输出12。

若k1=1，k2=3，代表询问这个区间里出现次数第1少的权值中第3小的，则应该输出3。

输入格式

第一行包括一个整数n，代表序列的长度。

第二行包括n个整数a1...an，代表该序列。

第三行包括一个整数m，代表询问的次数。

接下来m行，每行包括4个整数l，r，k1，k2，询问al...ar中出现次数第k1少的权值中第k2小的。

输出格式

对于每个询问，仅输出一行，包括一个整数，代表你的回答。

样例

样例输入

【输入样例1】
10
3 6 6 8 3 10 1 6 5 6
10
4 7 1 2
5 7 1 1
5 6 1 2
2 6 2 1
8 9 1 1
6 9 1 2
1 2 1 1
1 4 2 1
5 7 1 3
2 6 1 3

【输入样例2】
20
14 18 19 11 15 13 9 10 5 13 3 14 14 12 12 8 4 17 8 8
20
8 9 1 2
6 19 2 2
7 11 1 1
8 12 1 4
9 13 2 1
14 15 1 1
6 11 1 4
5 7 1 3
8 18 2 1
2 4 1 3
4 16 1 1
5 14 1 5
13 14 1 2
15 15 1 1
12 17 1 1
3 12 2 1
14 17 1 1
6 13 1 4
11 11 1 1
2 4 1 3

样例输出

【输出样例1】
3
1
10
6
5
5
3
6
10
10

【输出样例2】
10
12
3
13
14
12
10
15
12
19
3
12
14
12
4
13
4
10
3
19

数据范围与提示

【数据范围】

1<=n<=40000，

1<=ai<=n(1<=i<=n)，

1<=m<=40000，

1<=l<=r<=n，

保证k1,k2合法。

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium