poj2828

题解：

树状数组+二分

从后来的人往前面扫

当前人最终位置=当前人插入时候的位置+后来有多少人排在它的前面

二分最终答案

然后树状数组上当前位置加一

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200005;
int a[N],b[N],n,q[N],ans[N];
int js(int x)
{
    int ans=0;
    for (;x;x-=x&-x)ans+=b[x];
    return ans;
}
void inster(int x)
{
    for (;x<=n;x+=x&-x)b[x]++;
}
int main()
{
    while (~scanf("%d",&n))
     {
         memset(b,0,sizeof b);
         for (int i=1;i<=n;i++)scanf("%d%d",&a[i],&q[i]),a[i]++;
         for (int i=n;i;i--)
          {
              int l=a[i],r=n;
              while (l<r)
               {
                   int mid=(l+r)/2;
                   if (js(mid)+a[i]>mid)l=mid+1;
                   else r=mid;
               }
              ans[l-1]=q[i];
            inster(l); 
          }
         for (int i=0;i<n;i++)printf("%d ",ans[i]);
        puts(""); 
     }
}