欧美激情1区,999在线观看精品免费不卡网站,欧美一区二区三区婷婷月色

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 閱讀(190) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P2104