题目背景

小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。

题目描述

小卡家有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 21 5 2 6 3 7 41 5 32 7 1

输出样例#1： 

32

Solution：

　　本题我要吐槽洛谷数据～～（我的锅啊～～！我算错复杂度了，我的这个方法复杂度是$O(nlogn)$，因为本题题面中说道区间互不包含）

　　码了一个莫队+权值线段树维护，时间复杂度$O(n\sqrt{n}logn)$（错了，是$O(nlogn)$），结果$AC$还进了最优解第一页。

　　首先就是常规的莫队离线，记录区间，排序。

　　对原数离散化，再构建权值线段树，每次维护一个数的增减，查询整个区间第$k$大，记录$ans$就$OK$了。

代码：

 

#include
     
      #define il inline#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using 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
      
       '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(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\n",ans[i]);    return 0;}