题目背景
小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。
题目描述
小卡家有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
Solution：
本题我要吐槽洛谷数据～～（我的锅啊～～！我算错复杂度了，我的这个方法复杂度是$O(nlogn)$，因为本题题面中说道区间互不包含）
码了一个莫队+权值线段树维护，时间复杂度$O(nsqrt{n}logn)$（错了，是$O(nlogn)$），结果$AC$还进了最优解第一页。
首先就是常规的莫队离线，记录区间，排序。
对原数离散化，再构建权值线段树，每次维护一个数的增减，查询整个区间第$k$大，记录$ans$就$OK$了。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int N=300005; int tr[N<<2],n,m,pos[N],a[N],ans[N]; struct node{ int l,r,k,id; }q[N]; struct numm{ int v,id; bool operator < (const numm a)const{return v<a.v;} }nm[N]; il bool cmp(node a,node b){return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l;} il int gi(){ int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=a*10+x-48,x=getchar(); return f?-a:a; } il void pushup(int rt){tr[rt]=tr[rt<<1]+tr[rt<<1|1];} il void update(int k,int c,int l,int r,int rt){ if(l==k&&r==k){tr[rt]+=c;return;} tr[rt]+=c; int m=l+r>>1; if(k<=m)update(k,c,lson); else update(k,c,rson); pushup(rt); } il int query(int k,int l,int r,int rt){ if(l==r)return l; int m=l+r>>1; if(tr[rt<<1]>=k)return query(k,lson); else return query(k-tr[rt<<1],rson); } int main(){ n=gi(),m=gi(); int s=int(sqrt(n)); for(int i=1;i<=n;i++)nm[i].v=gi(),nm[i].id=i,pos[i]=(i-1)/s+1; sort(nm+1,nm+n+1); for(int i=1;i<=n;i++)a[nm[i].id]=i; for(int i=1;i<=m;i++)q[i].l=gi(),q[i].r=gi(),q[i].k=gi(),q[i].id=i; sort(q+1,q+m+1,cmp); for(int i=1,l=1,r=0;i<=m;i++){ while(r<q[i].r)update(a[++r],1,1,n,1); while(r>q[i].r)update(a[r--],-1,1,n,1); while(l<q[i].l)update(a[l++],-1,1,n,1); while(l>q[i].l)update(a[--l],1,1,n,1); ans[q[i].id]=nm[query(q[i].k,1,n,1)].v; } for(int i=1;i<=m;i++)printf("%d ",ans[i]); return 0; }