划分树toj2722

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 100005

int tree[20][MAX]; //表示每一层每个位置的值

int sorted[MAX]; //已排好序的序列

int toleft[20][MAX]; //表示它在一个子区间内从1到i有多少个数会被分到左边

void build(int l,int r,int dep) //建树

{

if(l==r) return;

int mid,i,same,lpos,rpos;

mid=(l+r)>>1;

for(i=l,same=0;i<=r;i++)

same+=(tree[dep][i]<sorted[mid]);

same=mid-l+1-same; //same表示和中间的数大小一样且会被分到左边的数的个数

for(i=l,lpos=l,rpos=mid+1;i<=r;i++)

{

if(tree[dep][i]<sorted[mid]) //比中间的数小，显然应该放在左边

tree[dep+1][lpos++]=tree[dep][i];

else if(tree[dep][i]==sorted[mid]&&same) //和中间的数一样大，但是same不为0，即还可以放一样的，则放在左边

{

tree[dep+1][lpos++]=tree[dep][i];

same--;

}

else //比中间的数大，显然要放在右边

tree[dep+1][rpos++]=tree[dep][i];

toleft[dep][i]=toleft[dep][l-1]+lpos-l; //从1到i被放在左边的数的个数

}

build(l,mid,dep+1); //递归的去做

build(mid+1,r,dep+1);

}

//查询某个区间第K大数，L,R是大区间，l和r是要查询的小区间

int query(int L,int R,int l,int r,int dep,int k)

{

//关键是newl和newr的计算，要仔细

if(l==r) return tree[dep][l];

int mid,i,newl,newr,cnt;

mid=(L+R)>>1;

cnt=toleft[dep][r]-toleft[dep][l-1];

if(cnt>=k) //有大于或等于k个数倍放在左边，则上左边去找

{

//L+在要查询的这段区间之前，这些数被放到左边几个

newl=L+toleft[dep][l-1]-toleft[dep][L-1];

//做端点加上会被放到左边的这几个数-1，就是右端点

newr=newl+cnt-1;

return query(L,mid,newl,newr,dep+1,k);

}

else

{ //先找出右端点通过右端点得到左端点。

newr=r+toleft[dep][R]-toleft[dep][r];

newl=newr-(r-l-cnt);

return query(mid+1,R,newl,newr,dep+1,k-cnt);

}

int main()

{

int n,q,i,a;

while(scanf("%d%d",&n,&q)!=EOF)

{

memset(tree,0,sizeof(tree));

for(i=1;i<=n;i++)

{

scanf("%d",&tree[0][i]);

sorted[i]=tree[0][i];

}

sort(sorted+1,sorted+n+1);

build(1,n,0);

for(i=0;i<q;i++)

{

int b,k;

scanf("%d%d%d",&a,&b,&k);

printf("%d\n",query(1,n,a,b,0,k));

}

return 0;

}

posted on 2010-07-31 02:12 YUANZX 阅读(349) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

划分树toj2722

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜