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; }