513
POJ 2828 单点更新
题意：给出N个人要查入队伍中的位置，按照输入的顺序，求最后队伍的先后顺序。
先把输入存起来，从后往前插入，前一个序号就代表前面有几个人，线段树内记录当前位置是否被占了，找低Num+1个空位坐下就行，查询函数返回空总和为num+1的位置。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=200005;
int node[maxn<<2];
int yl[maxn][2],q[maxn];
void build(int l,int r,int rt)
{
node[rt]=r-l+1;
if(l==r)
return;
int m=(l+r)>>1;
build(lson);
build(rson);
}
int query(int pos,int l,int r,int rt)
{
node[rt]--;
if(l==r)
{
return l;
}
int m=(l+r)>>1;
int ret=0;
if(pos<=node[rt<<1])
ret=query(pos,lson);
else
ret=query(pos-node[rt<<1],rson);
return ret;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
build(1,n,1);
for(int i=0; i<n; i++)
scanf("%d%d",&yl[i][0],&yl[i][1]);
for(int i=n-1; i>=0; i--)
q[query(yl[i][0]+1,1,n,1)]=yl[i][1];
for(int i=1; i<=n; i++)
printf("%d%c",q[i],i!=n?' ':'\n');
}
return 0;
}
最后更新：2017-04-03 18:52:02