可怜的狗狗
题目背景
小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。
题目描述
小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。
可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间（i,j）不互相包含。
输入输出格式
输入格式：
第一行输入两个数n，m，你可以假设n<300001 并且 m<50001；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
分析：
$Noip$前复习一波$FHQ\_Treap$。
很模板了，求$k$小值，把询问区间排个序再依次处理就行了。
Code：
//It is made by HolseLee on 7th Nov 2018
//Luogu.org P1533
#include<bits/stdc++.h>
using namespace std; const int N=3e5+;
int n,m,tot,root,a[N],ch[N][],val[N],siz[N],p[N],ans[N];
struct Ques {
int l,r,k,id;
inline bool operator < (const Ques x) const {
return l==x.l ? r<x.r : l<x.l;
}
}q[N]; inline int read()
{
char ch=getchar(); int x=; bool flag=false;
while( ch<'' || ch>'' ) {
if( ch=='-' ) flag=true; ch=getchar();
}
while( ch>='' && ch<='' ) {
x=x*+ch-''; ch=getchar();
}
return flag ? -x : x;
} inline void pushup(int rt)
{
siz[rt]=siz[ch[rt][]]+siz[ch[rt][]]+;
} void split(int rt,int k,int &x,int &y)
{
if( !rt ) x=y=;
else {
if( val[rt]<=k ) x=rt, split(ch[rt][],k,ch[rt][],y);
else y=rt, split(ch[rt][],k,x,ch[rt][]);
pushup(rt);
}
} int merge(int x,int y)
{
if( !x || !y ) return x+y;
if( p[x]<p[y] ) {
ch[x][]=merge(ch[x][],y); pushup(x);
return x;
} else {
ch[y][]=merge(x,ch[y][]); pushup(y);
return y;
}
} inline int neo(int v)
{
siz[++tot]=; val[tot]=v;
p[tot]=rand();
return tot;
} inline void insert(int v)
{
int x,y;
split(root,v,x,y);
root=merge(merge(x,neo(v)),y);
} inline void delet(int v)
{
int x,y,z;
split(root,v,x,y);
split(x,v-,x,z);
z=merge(ch[z][],ch[z][]);
root=merge(merge(x,z),y);
} int Rank(int u,int k)
{
if( siz[ch[u][]]==k- ) return val[u];
else if( siz[ch[u][]]>=k ) return Rank(ch[u][],k);
return Rank(ch[u][],k-siz[ch[u][]]-);
} int main()
{
srand(time());
n=read(); m=read();
for(int i=; i<=n; ++i) a[i]=read();
for(int i=; i<=m; ++i) {
q[i].l=read(), q[i].r=read(), q[i].k=read();
q[i].id=i;
}
sort(q+,q+m+);
int L=, R=;
for(int i=; i<=m; ++i) {
while( R<q[i].r ) insert(a[++R]);
while( L<q[i].l ) delet(a[L++]);
ans[q[i].id]=Rank(root,q[i].k);
}
for(int i=; i<=m; ++i) printf("%d\n",ans[i]);
return ;
}