A22623.可怜的狗狗
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小卡家有 n 只狗,由于品种、年龄不同,每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比(漂亮值越低越漂亮),吃饭时,狗狗们会按顺序站成一排等着主人给食物。
可是嘉嘉真的很懒,他才不肯喂这么多狗呢,这多浪费时间啊,于是他每次就只给第 i 只到第 j 只狗中第 k 漂亮的狗狗喂食(好狠心的人啊)。而且为了保证某一只狗狗不会被喂太多次,他喂的每个区间 [i,j] 不互相包含。
输入格式
第一行输入两个数 n,m, m 表示嘉嘉喂食的次数
第二行 n 个整数,表示第 i 只狗的漂亮值为 ai。
接下来 m 行,每行 3 个整数 i,j,k,表示询问这次喂食喂第 i 到第 j 只狗中第 k 漂亮的狗的漂亮值。
输出格式
m 行,每行一个整数,表示每一次喂的那只狗漂亮值为多少。
输入输出样例
输入#1
7 2 1 5 2 6 3 7 4 1 5 3 2 7 1
输出#1
3 2
说明/提示
1≤n≤3×105,1≤m≤5×104
P1533