巢穴

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   知识库   博问   管理