HDUnbsp;4251nbsp;Thenbsp;Famousnbsp;ICPCnbsp;Teamnbsp;Ag…

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4251

看了人家的结题报告才知道有划分树这种东东~ ~ ~

划分树

划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值

此题是模板题，就不说各种废话了，

代码：

#include<stdio.h>
#include<stdlib.h>
#define MAX 100001

int od[MAX],map[MAX];
int left[20][MAX],val[20][MAX];

int cmp(const void *a,const void *b)
{
   return map[*(int *)a] - map[*(int *)b];
}

void Build(int l,int r,int d)
{
   if(l==r)return;
   int i,mid=(l+r)>>1,p=0;
   for(i=l;i<=r;i++)
   {
       if(val[d][i] <= mid)
       {
           val[d+1][l+p]=val[d][i];
           left[d][i]=++p;
       }
       else
       {
           left[d][i]=p;
           val[d+1][mid+i+1-l-p]=val[d][i];
       }
   }
   Build(l,mid,d+1);
   Build(mid+1,r,d+1);
}

int search(int s,int e,int k,int l,int r,int d)
{
   if(l==r)return l;
   int mid=(l+r)>>1,ss,ee;
   ss=s==l?0:left[d][s-1];
   ee=left[d][e];
   if( ee-ss >=k)
       return search(l+ss,l+ee-1,k,l,mid,d+1);
   else return search(mid+1+(s-l-ss),mid+1+(e-l-ee),k-(ee-ss),mid+1,r,d+1);
}

int main()
{
   int n,i,m,l,r,ans=0;
   while(scanf("%d",&n)!=EOF)
   {
       for(i=1;i<=n;i++)
       {
           scanf("%d",&map[i]);
           od[i]=i;
       }
       qsort(od+1,n,sizeof(od[0]),cmp);
       for(i=1;i<=n;i++)
           val[0][od[i]]=i;
       Build(1,n,0);
       scanf("%d",&m);
       printf("Case %d:\n",++ans);
       while(m--)
       {
           scanf("%d%d",&l,&r);
           printf("%d\n",map[od[search(l,r,(r-l)/2+1,1,n,0)]]);
       }
   }
   return 0;
}