ZOJ 3635線分樹
1361 ワード
セグメントツリーは区間がどれだけ空いているかを維持し、X番目の空いている位置がどこにあるかを問い合わせるたびにsum[rt]>=Xは左区間に、sum[rt]
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 55555;
int n,m;
int sum[maxn<<2],a[maxn];
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
if (l==r) {sum[rt]=1;return;}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
int update(int l,int r,int rt,int cnt)
{
int ret,m=(l+r)>>1;
if(l==r)
{
sum[rt]=0;
return l;
}
if(cnt<=sum[rt<<1]) ret=update(lson,cnt);
else ret=update(rson,cnt-sum[rt<<1]);
pushup(rt);
return ret;
}
int main()
{
int x;
while(~scanf("%d",&n))
{
build(1,n,1);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[i]=update(1,n,1,x);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
if(i==1) printf("%d",a[x]);
else printf(" %d",a[x]);
}
puts("");
}
return 0;
}