板子，的题解写的真好

ps:看了看attack大佬的板子……跑的飞快……

然后抄了抄……慢的要命（评测机玄学问题？）

真不知道大佬常数怎么写的……

更神仙的是大佬居然都不先建树直接加点→_→

怎么过的orz

1 // luogu-judger-enable-o2 2 //minamoto 3 #include
     
       4 #define N 200005 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<15,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<15],*p1=buf,*p2=buf; 8 inline int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 int sum[N<<5],L[N<<5],R[N<<5];19 int a[N],b[N],t[N];20 int n,q,m,cnt=0;21 int build(int l,int r){22     int rt=++cnt;23     sum[rt]=0;24     if(l
      
       >1;26         L[rt]=build(l,mid);27         R[rt]=build(mid+1,r);28     }29     return rt;30 }31 int update(int last,int l,int r,int x){32     int rt=++cnt;33     L[rt]=L[last],R[rt]=R[last],sum[rt]=sum[last]+1;34     if(l
       
        >1;36         if(x<=mid) L[rt]=update(L[last],l,mid,x);37         else R[rt]=update(R[last],mid+1,r,x);38     }39     return rt;40 }41 int query(int u,int v,int l,int r,int k){42     if(l>=r) return l;43     int x=sum[L[v]]-sum[L[u]];44     int mid=(l+r)>>1;45     if(x>=k) return query(L[u],L[v],l,mid,k);46     else return query(R[u],R[v],mid+1,r,k-x);47 }48 int main(){49     //freopen("testdata.in","r",stdin);50     n=read(),q=read();51     for(int i=1;i<=n;++i)52     b[i]=a[i]=read();53     sort(b+1,b+1+n);54     m=unique(b+1,b+1+n)-b-1;55     t[0]=build(1,m);56     for(int i=1;i<=n;++i){57         int k=lower_bound(b+1,b+1+m,a[i])-b;58         t[i]=update(t[i-1],1,m,k);59     }60     while(q--){61         int x,y,z;62         x=read(),y=read(),z=read();63         int k=query(t[x-1],t[y],1,m,z);64         printf("%d\n",b[k]);65     }66     return 0;67 }
       
      
     

然后是照着attack大佬的板子写的

算了以后用这个板子

1 // luogu-judger-enable-o2 2 // luogu-judger-enable-o2 3 //minamoto 4 #include
     
       5 #define N 200005 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){10     #define num ch-'0'11     char ch;bool flag=0;int res;12     while(!isdigit(ch=getc()))13     (ch=='-')&&(flag=true);14     for(res=num;isdigit(ch=getc());res=res*10+num);15     (flag)&&(res=-res);16     #undef num17     return res;18 }19 char obuf[1<<24],*o=obuf;20 void print(int x){21     if(x>9) print(x/10);22     *o++=x%10+48;23 }24 int sum[N<<5],L[N<<5],R[N<<5];25 int a[N],b[N],t[N];26 int n,q,m,cnt=0;27 void update(int last,int &now,int l,int r,int x){28     if(!now) now=++cnt;29     sum[now]=sum[last]+1;30     if(l==r) return;31     int mid=(l+r)>>1;32     if(x<=mid) R[now]=R[last],update(L[last],L[now],l,mid,x);33     else L[now]=L[last],update(R[last],R[now],mid+1,r,x);34 }35 int query(int u,int v,int l,int r,int k){36     if(l>=r) return l;37     int x=sum[L[v]]-sum[L[u]];38     int mid=(l+r)>>1;39     if(x>=k) return query(L[u],L[v],l,mid,k);40     else return query(R[u],R[v],mid+1,r,k-x);41 }42 int main(){43     //freopen("testdata.in","r",stdin);44     n=read(),q=read();45     for(int i=1;i<=n;++i)46     b[i]=a[i]=read();47     sort(b+1,b+1+n);48     m=unique(b+1,b+1+n)-b-1;49     for(int i=1;i<=n;++i){50         int k=lower_bound(b+1,b+1+m,a[i])-b;51         update(t[i-1],t[i],1,m,k);52     }53     while(q--){54         int x,y,z;55         x=read(),y=read(),z=read();56         int k=query(t[x-1],t[y],1,m,z);57         print(b[k]);58         *o++='\n';59     }60     fwrite(obuf,o-obuf,1,stdout);61     return 0;62 }