poj 2104

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<vector>
  5 #include<cstdio>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<map>
  9 #include<set>
 10 #include<ctime>
 11 using namespace std;
 12 #define re(i,n)     for(int i=0;i<n;i++)
 13 #define RE(i,n)     for(int i=n-1;i;i--)
 14 #define REP(i,n)    for(int i=n;i;i--)
 15 #define rep(i,n)    for(int i=1;i<=n;i++)
 16 #define repx(i,a,b) for(int i=a;i<=b;i++)
 17 #define repy(i,a,b) for(int i=a;i>=b;i--)
 18 #define ms(i,a)     memset(a,i,sizeof(a))
 19 #define sz(x)       (x.size())
 20 #define pb          push_back
 21 #define sqr(x)      ((x)*(x))
 22 #define vi          vector<int>
 23 #define LL           long long
 24 #define pi          pair<int,int>
 25 #define mp          make_pair
 26 #define lch         (o<<1)
 27 #define rch         (o<<1|1)
 28 #define mid         (l+r)/2
 29 inline void  read(int &x){
 30     int w=0; char ch=0; x=0;
 31     while(ch<‘0‘ || ch>‘9‘) {w|=ch==‘-‘;ch=getchar();}
 32     while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
 33     if (w) x=-x;
 34 }
 35 
 36 inline void write(int x){
 37     if(x<0) putchar(‘-‘),x=-x;
 38     if(x>9) write(x/10);
 39     putchar(x%10+‘0‘);
 40 }
 41 int const maxn=100003;
 42 int const inf=1e9;
 43 struct node{
 44     int x,num;
 45     bool operator < ( const node &rhs) const{
 46         return x<rhs.x;
 47     }
 48 }a[maxn];
 49 
 50 struct query{
 51     int x,y,id,cnt,k;
 52 }q[maxn],tmp[maxn];
 53 int n,m,ans[maxn],t[maxn];
 54 void calc(int l,int r,int al,int Mid){
 55     int L=1, R=n+1;
 56     while (L<R){
 57         int M=(L+R)/2;
 58         if (a[M].x>=al) R=M;
 59         else L=M+1;
 60     }
 61     for(int i=R;i<=n && a[i].x<=Mid;i++)
 62         for(int j=a[i].num;j<=n; j+= (j&-j) ) t[j]++;
 63     for(int i=l;i<=r;i++){
 64         q[i].cnt=0;
 65         for(int j=q[i].y; j; j-=(j&-j)) q[i].cnt+=t[j];
 66         for(int j=q[i].x-1;j;j-=(j&-j)) q[i].cnt-=t[j];
 67     }
 68     for(int i=R;i<=n && a[i].x<=Mid;i++)
 69         for(int j=a[i].num;j<=n;j+=(j&-j)) t[j]--;
 70 }
 71 void solve(int  l,int  r,LL  al,LL  ar){
 72     if(al==ar){
 73         repx(i,l,r) ans[q[i].id]=al; return;
 74     }
 75     int  Mid=al+(ar-al)/2;
 76     calc(l,r,al,Mid);
 77     int p1=l,p2=r;
 78     for(int i=l;i<=r;i++)
 79         if (q[i].cnt>=q[i].k) tmp[p1++]=q[i];
 80         else q[i].k-=q[i].cnt,tmp[p2--]=q[i];
 81     for(int i=l;i<=r;i++) q[i]=tmp[i];
 82     if(l<=p1-1) solve(l,p1-1,al,Mid);
 83     if(p2+1<=r) solve(p2+1,r,Mid+1,ar);
 84 }
 85 
 86 int main(){
 87     scanf("%d%d",&n,&m);
 88     rep(i,n){
 89         scanf("%d",&a[i].x);
 90         a[i].num=i;
 91     }
 92     a[n+1].x=2*inf;
 93     sort(a+1,a+n+1);
 94     rep(i,m){
 95         scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].k);
 96         q[i].id=i;
 97     }
 98     solve(1,m,-inf,inf);
 99     rep(i,m) printf("%d\n",ans[i]);
100     return 0;
101 }