#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int T[121][110001];
int a[110001];
int n,m;

void buildkth(int dep,int l,int r){
     int mid=(l+r)/2;
     if (l<r){
              buildkth(dep+1,l,mid);
              buildkth(dep+1,mid+1,r);
     }
     else {T[dep][l]=a[l];return;}
     
     //归并
     
     int i=l;int j=mid+1;int k=l-1;
     while (i<=mid || j<=r){
           k++;
           
           if ((i<=mid && T[dep+1][i]<T[dep+1][j]) || j>r){
              T[dep][k]=T[dep+1][i++];
           }
           else
           if ((j<=r && T[dep+1][i]>=T[dep+1][j]) || i>mid){
              T[dep][k]=T[dep+1][j++];
           }
     }
}

int total(int ll,int rr,int data,int dep,int l,int r){
    if (ll==l && rr==r){
              int x=l;int y=r;int ans=l-1;
              while (x<=y){
                    int mid=(x+y)/2;
                    if (T[dep][mid]<data){x=mid+1;ans=mid;}
                    else y=mid-1;
              }
              return ans-l+1;
    }
    int mid=(l+r)/2;int tot=0;
    if (ll<=mid)
       tot+=total(ll,min(rr,mid),data,dep+1,l,mid);
    if (rr>mid)
       tot+=total(max(ll,(mid + 1)),rr,data,dep+1,mid+1,r);
    return tot;
}

int findkth(int l1,int r1,int k){
    int l=1;int r=n;
    int ans=1;
    while (l<=r){
          int mid=(l+r)/2;
          int xp=total(l1,r1,T[0][mid],0,1,n);
          if (xp<=k){
             ans=mid;
             l=mid+1;
          }
          else r=mid-1;
    }
    return T[0][ans];
}
             
int main(){
    
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    buildkth(0,1,n);
    
    int l,r,k;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",findkth(l,r,k-1));
    }
}

     

• Re:貌似是这道题的询问多。。我划分树2104 600+ms，这题1800+ms (2040) proverbs 2012-07-30 14:08:30