ORZ主席，这可持久化数据结构真是碉堡了！~
PS：这两个题的读入是不同的。。。
View Code
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 7 #define N 100010 8 9 using namespace std; 10 11 int h[N<<5],ls[N<<5],rs[N<<5],sum[N<<5]; 12 int cnt,n,m; 13 int a[N],bh[N]; 14 15 inline int newnode(int s,int l,int r) 16 { 17 ++cnt; 18 sum[cnt]=s; ls[cnt]=l; rs[cnt]=r; 19 return cnt; 20 } 21 22 inline void build(int l,int r,int &rt) 23 { 24 rt=newnode(0,0,0); 25 if(l==r) return; 26 int mid=(l+r)>>1; 27 build(l,mid,ls[rt]); 28 build(mid+1,r,rs[rt]); 29 } 30 31 inline void updata(int last,int pos,int l,int r,int &rt) 32 { 33 rt=newnode(sum[last]+1,ls[last],rs[last]); 34 if(l==r) return; 35 int mid=(l+r)>>1; 36 if(pos<=mid) updata(ls[last],pos,l,mid,ls[rt]); 37 else updata(rs[last],pos,mid+1,r,rs[rt]); 38 } 39 40 inline int query(int st,int ed,int l,int r,int k) 41 { 42 if(l==r) return l; 43 int mid=(l+r)>>1; 44 int tmp=sum[ls[ed]]-sum[ls[st]]; 45 if(k<=tmp) return query(ls[st],ls[ed],l,mid,k); 46 else return query(rs[st],rs[ed],mid+1,r,k-tmp); 47 } 48 49 inline void read() 50 { 51 cnt=0; 52 for(int i=1;i<=n;i++) 53 { 54 scanf("%d",&a[i]); 55 bh[i]=a[i]; 56 } 57 } 58 59 inline void go() 60 { 61 sort(bh+1,bh+1+n); 62 int num=unique(bh+1,bh+1+n)-bh-1; 63 for(int i=1;i<=n;i++) a[i]=lower_bound(bh+1,bh+1+num,a[i])-bh; 64 build(1,num,h[0]); 65 for(int i=1;i<=n;i++) updata(h[i-1],a[i],1,num,h[i]); 66 int l,r,k; 67 while(m--) 68 { 69 scanf("%d%d%d",&l,&r,&k); 70 printf("%d\n",bh[query(h[l-1],h[r],1,num,k)]); 71 } 72 } 73 74 int main() 75 { 76 while(scanf("%d%d",&n,&m)!=EOF) read(),go(); 77 return 0; 78 }