学步园

给N 个人 给出位置 每个人的价值 然后求出最后的价值的顺序

a1 a2 a3 a4 如果 后面的n位置和前面的人位置相等 那么前面的人要后移一位

这样只要倒着处理就好 从最后一位开始更新

建树时父节点存的是子节点可以放多少人 所以 r - l + 1

这个可以画图理解一下

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
int const MAXN = 200010;
int ans[MAXN];
struct Tree{
    int l,r;
    int s,v;
}tree[MAXN<<2];
struct Point{
    int pos,v;
}p[MAXN];
void Build(int l,int r,int rt){
    tree[rt].s = r - l + 1;
    if(l == r) return ;
    int m = (l + r)>>1;
    Build(Lson);
    Build(Rson);
}
void Update(int c,int x,int l,int r,int rt){
    tree[rt].s--;
    if(l == r){
        ans[l] = c;
        return ;
    }
    int m = (l + r)>>1;
    if(tree[rt<<1].s >= x)Update(c,x,Lson);
    else Update(c,x - tree[rt<<1].s,Rson);
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        Build(1,n,1);
        memset(ans,0,sizeof(ans));
        for(int i = 0;i < n;i++){
            scanf("%d%d",&p[i].pos,&p[i].v);
        }
        for(int i = n - 1;i >= 0;i--){
            Update(p[i].v,p[i].pos + 1,1,n,1);
        }
        for(int i = 1;i <= n - 1;i++){
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[n]);
    }
    return 0;
}