题目链接：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;
}