hdu 2665 （poj 2104） 划分树
poj2104题目要求弱一些，n个数是不同的。hdu2665中没有这样的限制。所以在划分左右区间时需要处理一下相同的数怎么划分。
[cpp]
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define M 100010
using namespace std;
int tr[20][M],num[20][M],sorted[M];
void build(int l,int r,int d)
{
if(l==r) return ;
int m=(l+r)/2;
int lp=l,rp=m+1;
int h=1;
for(int j=m-1;j>=l;j--)
{
if( sorted[j]==sorted[m] )
h++;
else break;
}
for(int i=l;i<=r;i++)
{
num[d][i]=num[d][i-1];
if( tr[d][i]<sorted[m] && lp<=m)
{
tr[d+1][lp++]=tr[d][i];
num[d][i]++;
}
else
if( tr[d][i]==sorted[m])
{
if( h>0 ) { tr[d+1][lp++]=tr[d][i],h--; num[d][i]++; }
else tr[d+1][rp++]=tr[d][i];
}
else
{
tr[d+1][rp++]=tr[d][i];
}
}
build(l,m,d+1);
build(m+1,r,d+1);
}
int query(int s,int t,int k,int l,int r,int d)
{
int m=(l+r)/2;
if(s==t) return tr[d][s];
int p=num[d][t]-num[d][s-1];
int sl=num[d][s-1]-num[d][l-1];
if( p>=k )
{
return query(l+sl,l+sl+p-1,k,l,m,d+1);
}
else
{
int b=s-l-sl; int bb=t-s+1-p;
return query( m+b+1,m+b+bb,k-p,m+1,r,d+1);
}
}
int main()
{
int n,m,i,j,k,s,t,T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(num,0,sizeof(num));
memset(tr,0,sizeof(tr));
for(i=1;i<=n;i++)
{
scanf("%d",&sorted[i]);
tr[0][i]=sorted[i];
}
sort(sorted+1,sorted+n+1);
build(1,n,0);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&s,&t,&k);
int ans=query(s,t,k,1,n,0);
printf("%d\n",ans);
}
}
return 0;
}
补充：软件开发 , C++ ,
