线段树典型例题--poj2828
逆序处理。
注意到如果逆序插入，则每次插入的位置都是第x个空位。
所以可以用线段树来寻找第x个合法位置
【代码】
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>using namespace std;const int N=200005;int sum[N*3],pos[N],val[N],p[N];int n;void build(int i,int l,int r){ sum[i]=r-l+1; if (l==r) return; int mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r);}void ins(int i,int l,int r,int pos,int val){ sum[i]--; if (l==r) { p[l]=val; return; } int mid=(l+r)/2; if (sum[i*2]-pos>=0) ins(i*2,l,mid,pos,val); else ins(i*2+1,mid+1,r,pos-sum[i*2],val);}int main(){ int i; freopen("in","r",stdin); while (scanf("%d",&n)!=EOF) { for (i=1;i<=n;i++) scanf("%d%d",&pos[i],&val[i]); build(1,1,n); for (i=n;i>=1;i--) ins(1,1,n,pos[i]+1,val[i]); for (i=1;i<n;i++) printf("%d ",p[i]); printf("%d\n",p[n]); }}