巢穴

about:blank

P2104

归并排序+线段树+二分.
二分写的我比较恶心..

#include <iostream>
#include 
<stdio.h>
using namespace std;

struct node
{
       
int l,r,t;
}
tree[400001];
const int MAXN=100001;
int n,qn;
int num[19][MAXN];

int top=0;
void mergesort(int l,int r,int t,int p)
{
 
if (l==r)
 
{
          
  num[t][l]
=num[0][l];
  tree[p].t
=t;
  tree[p].l
=l;
  tree[p].r
=r;
  
return;  
 }

 
int mid=(l+r)/2;
 mergesort(l,mid,t
+1,p*2);
 mergesort(mid
+1,r,t+1,p*2+1); 
 
int l1=l,r1=mid+1,v=l;
 
while(v<=r)
 
{
  
if ((num[t+1][l1]<num[t+1][r1]||r1>r)&&l1<=mid) {num[t][v++]=num[t+1][l1++];continue;}
  
if ((num[t+1][r1]<num[t+1][l1]||l1>mid)&&r1<=r) {num[t][v++]=num[t+1][r1++];}
 }

 tree[p].l
=l;
 tree[p].r
=r;
 tree[p].t
=t;
}

int find(int l,int r,int value,int p)
{
 
int left_=tree[p].l;
 
int right_=tree[p].r;
 
int mid=(left_+right_)/2;
 
int count=0;
 
if (left_>=l&&right_<=r)
 
{
  
int ll=left_,rr=right_,t=tree[p].t;
  
int mm;
  
while(ll<rr)
  
{
     mm
=(ll+rr+1)/2;
     
if (num[t][mm]<value) ll=mm; else rr=mm-1;     
  }
       
  count
=ll-left_;
  
if (value>num[t][ll]) count++;
  
return count;
 }

 
else
 
{
  
if (l<=mid) count+=find(l,r,value,p*2);
  
if (r>=mid+1) count+=find(l,r,value,p*2+1);
 }

 
return count;
}

int main()
{

    cin
>>n>>qn;
    
for (int i=1;i<=n;i++)
    
{
     cin
>>num[0][i];
    }

    top
++;
    mergesort(
1,n,top,1);
    
for (int i=1;i<=qn;i++)
    
{
        
int l,r,k;
        cin
>>l>>r>>k;
        k
--;
        
int lp=1,rp=n;
        
int mid;
        
while(lp<rp)
        
{
         mid
=(lp+rp+1)/2;
         
int kk=find(l,r,num[1][mid],1);
         
if (kk<=k) lp=mid;
         
else rp=mid-1;
        }


        cout
<<num[1][lp]<<endl;
    }

     
     
     system(
"pause");
    
    
    
return 0;
}

posted on 2009-11-09 12:35 Vincent 阅读(179) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理