#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <set> #include<map> #include<ctime> using namespace std; const int N=100009; const int M=50009; int n,m,a[N],ans[M]; int hash[N]; map<int,int> Map; struct point { int a,num,h; }p[N]; struct Inv { int a,b,k,num; }inv[M]; bool cmp(Inv x,Inv y) { return x.b<y.b; } bool cmp2(point x,point y) { return x.a<y.a; } bool cmp3(point x,point y) { return x.num<y.num; } int ar[N]; inline int lowb(int t){return t&(-t) ;} void add(int i,int v) { for(;i<N;ar[i]+=v,i+=lowb(i)); } int sum(int k) { int pos=0,cnt=0; for(int i=20;i>=0;i--) { pos+=1<<i; if(pos>=N||cnt+ar[pos]>=k)pos-=1<<i; else cnt+=ar[pos]; } return pos+1; } /* 二分法得到第k小数************************************************** int sum(int i) { int s=0; for(;i>0;s+=ar[i],i-=lowb(i)); return s; } int get(int k) { int l=0,r=N; while(l<r-1) { int mid=(l+r)>>1; int f=sum(mid); if(f>=k) { r=mid; } else l=mid; } return r; } **************************************************************************/ int main() { scanf("%d%d",&n,&m); memset(ar,0,sizeof(ar)); for(int i=1;i<=n;i++) { scanf("%d",&p[i].a); p[i].num=i; } sort(p+1,p+n+1,cmp2); for(int i=1;i<=n;i++) { p[i].h=i; hash[i]=p[i].a; } sort(p+1,p+n+1,cmp3); for(int i=0;i<m;i++) { scanf("%d%d%d",&inv[i].a,&inv[i].b,&inv[i].k); inv[i].num=i; } sort(inv,inv+m,cmp); int s=inv[0].a,e=inv[0].a; for(int i=0;i<m;i++) { while(inv[i].a>s) { add(p[s].h,-1); s++; } while(e<=inv[i].b) { add(p[e].h,1); e++; } ans[inv[i].num]=hash[sum(inv[i].k)]; } for(int i=0;i<m;i++) printf("%d\n",ans[i]); }
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <set> #include<map> #include<ctime> using namespace std; const int N=100009; const int M=50009; int n,m,a[N],ans[M]; int hash[N]; struct point { int a,num,h; }p[N]; struct Inv { int a,b,k,num; }inv[M]; bool cmp(Inv x,Inv y) {return x.b<y.b;} bool cmp2(point x,point y) {return x.a<y.a;} bool cmp3(point x,point y) {return x.num<y.num;} //*************线段树****************************************************** struct Tree { int L,R,V; int lazy; }tree[4*N]; void create(int t,int L,int R) { int mid=(L+R)>>1; int l=2*t; int r=2*t+1; tree[t].L=L; tree[t].R=R; tree[t].V=0; tree[t].lazy=0; if(L<R) { create(l,L,mid); create(r,mid+1,R); } } void down(int t) { int l=2*t; int r=2*t+1; if(tree[t].lazy==0)return ; if(tree[t].L<tree[t].R) { tree[l].V+=tree[t].lazy; tree[r].V+=tree[t].lazy; tree[l].lazy+=tree[t].lazy; tree[r].lazy+=tree[t].lazy; } tree[t].lazy=0; } void insert(int t,int L,int R,int v) { int l=2*t; int r=2*t+1; int mid=(tree[t].L+tree[t].R)>>1; if(tree[t].L==L&&tree[t].R==R) { tree[t].V+=v; if(L<R) tree[t].lazy+=v; return ; } down(t); if(L>mid)insert(r,L,R,v); else if(R<=mid)insert(l,L,R,v); else { insert(l,L,mid,v); insert(r,mid+1,R,v); } } int query(int t,int L) { int l=2*t; int r=2*t+1; int mid=(tree[t].L+tree[t].R)>>1; if(tree[t].L==tree[t].R) return tree[t].V; down(t); if(L<=mid)return query(l,L); else return query(r,L); } //******************************************************************* int get(int k) { int l=0,r=n,mid; while(l<r-1) { mid=(l+r)>>1; int t=query(1,mid); if(t>=k) r=mid; else l=mid; } return l; } int main() { scanf("%d%d",&n,&m); create(1,1,n+1); for(int i=1;i<=n;i++) { scanf("%d",&p[i].a); p[i].num=i; } sort(p+1,p+n+1,cmp2); for(int i=1;i<=n;i++) { p[i].h=i; hash[i]=p[i].a; } sort(p+1,p+n+1,cmp3); for(int i=0;i<m;i++) { scanf("%d%d%d",&inv[i].a,&inv[i].b,&inv[i].k); inv[i].num=i; } sort(inv,inv+m,cmp); int s=inv[0].a,e=inv[0].a; for(int i=0;i<m;i++) { while(inv[i].a>s) { insert(1,p[s].h+1,n+1,-1); s++; } while(e<=inv[i].b) { insert(1,p[e].h+1,n+1,1); e++; } ans[inv[i].num]=hash[get(inv[i].k)]; } for(int i=0;i<m;i++) printf("%d\n",ans[i]); }