题目链接:https://vjudge.net/problem/POJ-2828
题解:
正序不好排,所以我们倒序考虑
对于每个人要把它放在第 <nobr> pos[i] </nobr>个人之后,也就是在倒序的时候查找第 <nobr> pos[i]+1 </nobr>个空位,把它放进去即可,随便维护一个区间和,线段树瞎搞就好
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
using namespace std;
const int N=200010;
int pos[N],val[N],n,ans[N];
struct segtree
{
int l,r,sum;
}t[N*4+5];
void Build(int rt,int l,int r)
{
t[rt].l=l;
t[rt].r=r;
t[rt].sum=r-l+1;
if(l==r) return;
int m=(l+r)>>1;
Build(L(rt),l,m);
Build(R(rt),m+1,r);
}
int Query(int rt,int x)
{
t[rt].sum--;
if(t[rt].l==t[rt].r) return t[rt].l;
if(t[L(rt)].sum>=x) return Query(L(rt),x);
else return Query(R(rt),x-t[L(rt)].sum);
}
int main()
{
while(~scanf("%d",&n))
{
Build(1,1,n);
for(int i=1;i<=n;i++) scanf("%d%d",&pos[i],&val[i]);
for(int i=n;i;i--)
{
int p=Query(1,pos[i]+1);
ans[p]=val[i];
}
for(int i=1;i<n;i++) printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
}