题目背景

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

题目描述

小卡家有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

思路

这个题出题人的意图是卡主席树的空间，卡平衡树的常数，，，然后我平衡树挂的比较惨，主席树卡过了；

正解就是离线跑权值线段树；

代码实现

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn=3e5+10; 5 int n,k,sz,ts; 6 int a,b,c; 7 int s[maxn],hs[maxn],tt[maxn]; 8 struct tree{
   int s,mid,lp,rp;}t[maxn*25]; 9 void build(int l,int r,int k){10     t[k].mid=l+r>>1;11     if(l==r) return;12     t[k].lp=++ts,t[k].rp=++ts;13     build(l,t[k].mid,t[k].lp);14     build(t[k].mid+1,r,t[k].rp);15 }16 void put(int l,int r,int k,int nk,int p){17     t[nk]=(tree){t[k].s+1,t[k].mid};18     if(l==r) return;19     if(p<=t[nk].mid){20         t[nk].lp=++ts,t[nk].rp=t[k].rp;21         put(l,t[nk].mid,t[k].lp,t[nk].lp,p);22     }23     else{24         t[nk].rp=++ts,t[nk].lp=t[k].lp;25         put(t[nk].mid+1,r,t[k].rp,t[nk].rp,p);26     }27 }28 int search(int k,int nk,int v){29     if((t[k].lp==0)&&(t[k].rp==0)) return t[k].mid;30     int w=t[t[nk].lp].s-t[t[k].lp].s;31     if(v<=w) return search(t[k].lp,t[nk].lp,v);32     else return search(t[k].rp,t[nk].rp,v-w);33 }34 int main(){35     scanf("%d%d",&n,&k);36     for(int i=1;i<=n;i++){37         scanf("%d",&s[i]);38         hs[i]=s[i];39     }40     sort(hs+1,hs+n+1);41     sz=unique(hs+1,hs+n+1)-hs-1;42     build(1,sz,tt[0]);43     for(int i=1;i<=n;i++){44         int pos=lower_bound(hs+1,hs+sz+1,s[i])-hs;45         tt[i]=++ts;46         put(1,sz,tt[i-1],tt[i],pos);47     }48     for(int i=1;i<=k;i++){49         scanf("%d%d%d",&a,&b,&c);50         printf("%d\n",hs[search(tt[a-1],tt[b],c)]);51     }52     return 0;53 }