[cpp]
/*
求區間中間值
可以轉化為求kth值 所以用了劃分樹
直接套用了上一篇的函數
上篇有講解
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int srted[N];
struct node
{
int num[N];
int val[N];
}t[40];
int n,m;
void build(int l,int r,int d)//建樹 此樹並非由節點構成 而是由數組的一段構成 如：d層的l~r是一個節點
{
if(l==r) return;
int mid=(l+r)>>1;//取中間那個
int midd=srted[mid];
int same=mid-l+1,samed=0,zn=l-1,yn=mid,i;//same初識化為左孩子元素個數
//下面減去比midd小的(一定會進入左孩子裡邊) 剩下的就是==midd並且要進入左孩子的個數
//samed是已經插入的數目
//zn、yn是左右孩子的開始位置-1，下面會把元素分到兩個孩子的區域裡邊
for(i=l;i<=r;++i)
if(t[d].val[i]<midd) --same;
for(i=l;i<=r;++i)//有點像快排 大的放到後邊 小的放前邊 相等的看情況
{
if(i==l) t[d].num[i]=0;
else t[d].num[i]=t[d].num[i-1];
if(t[d].val[i]<midd)
{
++t[d].num[i];//這裡是統計從l到i有多少元素進入了左孩子 這是劃分樹主要用到的數據
t[d+1].val[++zn]=t[d].val[i];
}else if(t[d].val[i]>midd)//進入右孩子
{
t[d+1].val[++yn]=t[d].val[i];
}else
{
if(samed<same)//名額還沒有用完 放左孩子裡邊
{
++samed;
++t[d].num[i];
t[d+1].val[++zn]=t[d].val[i];
}else//方有孩子裡邊
t[d+1].val[++yn]=t[d].val[i];
}
}
build(l,mid,d+1);//建左右子樹
build(mid+1,r,d+1);
}
int query(int a,int b,int k,int l,int r,int d)//在d層[l,r]的節點裡查找[a,b]中的第k大值
{
if(a==b) return t[d].val[a];
int mid=(l+r)>>1;
int sx=t[d].num[a-1],sy=t[d].num[b];
if(a-1<l) sx=0;
if(sy-sx>=k)//[a,b]進入左子樹的元素>=k
return query(l+sx,l+sy-1,k,l,mid,d+1);
else
{
int s1=(a==1?0:a-l-sx);
int s2=(b-a+1)-(sy-sx);
int nk=k-(sy-sx);//前(sy-sx)大的元素在左子樹裡 剩下的在右子樹裡邊找
return query(mid+1+s1,mid+s1+s2,nk,mid+1,r,d+1);
}
}
int main()
{
int cas=1;
int i,a,b;
while(cin>>n)
{
cout<<"Case "<<cas++<<":"<<endl;
for(i=1;i<=n;++i)
{
cin>>srted[i];
t[0].val[i]=srted[i];
}
sort(srted+1,srted+1+n);
build(1,n,0);
cin>>m;
for(i=1;i<=m;++i)
{
cin>>a>>b;
cout<<query(a,b,(a+b)/2-a+1,1,n,0)<<endl;
}
}
}
作者：qq172108805
