JZOJ 1011. 【GDKOI2009模拟3】Zoo
題目
Description
JZ擁有一個很大的野生動物園。這個動物園坐落在一個狹長的山谷内,這個區域從南到北被劃分成N個區域,每個區域都飼養着一頭獅子。這些獅子從北到南編号為1,2,3,…,N。每頭獅子都有一個覓食能力值Ai,Ai越小覓食能力越強。飼養員西西決定對獅子進行M次投喂,每次投喂都選擇一個區間[I,J],從中選取覓食能力值第K強的獅子進行投喂。值得注意的是,西西不願意對某些區域進行過多的投喂,他認為這樣有悖公平。是以西西的投喂區間是互不包含的(即區間[1,10]不會與[3,4]或[5,10]同時存在,但可以與[9,11]或[10,20]一起)。同一區間也隻會出現一次。你的任務就是算出每次投喂後,食物被哪頭獅子吃掉了。
Input
第一行兩個整數N,M。
第二行N個整數為每隻獅子的覓食能力值。(1<=能力值<=maxlongint)。
此後M行,每行描述一次投喂。第t+2的三個數I,J,K表示在第t次投喂中,西西選擇了區間[I,J]内覓食能力值第K強的獅子進行投喂。
Sample Input
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1
Output
輸出檔案有M行,每行一個整數。第i行的整數表示在第i次投喂中吃到食物的獅子的覓食能力值。
Sample Output
3
2
Data Constraint
對于100%的資料,有1<=N<=100000,1<=M<=50000。
題解
這道題是十分裸的主席樹,隻要懂得主席樹的基本操作都會實作。
【主席樹】可持久化線段樹
注意覓食能力值過大,需要給它們進行離散化。
标程
#include<cstdio>
#include<cstring>
using namespace std;
int rt[100010],pr[100010],num=0;
struct
{
int l,r,sum;
}f[3000010];
struct
{
int id,s;
}a[100010];
void qsort(int l,int r)
{
int x=l,y=r,mid=a[(l+r)/2].s;
while(x<=y)
{
while(a[x].s<mid) x++;
while(a[y].s>mid) y--;
if(x<=y) a[0]=a[x],a[x]=a[y],a[y]=a[0],x++,y--;
}
if(x<r) qsort(x,r);
if(y>l) qsort(l,y);
}
void make(int v,int l,int r)
{
if(l==r)
{
f[v].sum=0;
if(v>num) num=v;
return;
}
else
{
int mid=(l+r)/2;
f[v].l=v*2,f[v].r=v*2+1;
make(v*2,l,mid);
make(v*2+1,mid+1,r);
}
}
void add(int v,int v1,int l,int r,int x)
{
if(l==r)
{
f[v1].sum++;
return;
}
else
{
int mid=(l+r)/2;
if(x<=mid)
{
f[v1].l=++num;
f[v1].r=f[v].r;
add(f[v].l,f[v1].l,l,mid,x);
}
else
{
f[v1].l=f[v].l;
f[v1].r=++num;
add(f[v].r,f[v1].r,mid+1,r,x);
}
f[v1].sum=f[f[v1].l].sum+f[f[v1].r].sum;
}
}
int find(int v,int v1,int l,int r,int k)
{
if(l==r) return a[l].s;
else
{
int mid=(l+r)/2,s1=f[f[v1].l].sum-f[f[v].l].sum,s2=f[f[v1].r].sum-f[f[v].r].sum;
if(s1>=k) return find(f[v].l,f[v1].l,l,mid,k);
else return find(f[v].r,f[v1].r,mid+1,r,k-s1);
}
}
int main()
{
int n,m,i,l,r,k,q;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++) scanf("%d",&a[i].s),a[i].id=i;
qsort(1,n);
for(i=1;i<=n;i++) pr[a[i].id]=i;
rt[0]=1;
make(1,1,n);
for(i=1;i<=n;i++)
{
rt[i]=++num;
add(rt[i-1],rt[i],1,n,pr[i]);
}
for(i=1;i<=q;i++)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",find(rt[l-1],rt[r],1,n,k));
}
return 0;
}