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