Poj2828 Buy Tickets(逆序思维+线段树)

POJ2828

题意

$n$个人,给你$n$次操作

第$i$次操作表示编号$pos$的人插队到队伍第$x$个人后面了

问最后队伍的编号顺序

乍一看以为是链表裸题,但是发现查找第$x$个人会非常慢

结果题解十分巧妙

倒序考虑,因为最后面插入的人的位置是永远固定的

那么倒序考虑插入到第$x$个人后面说明前面要留刚好$x$个空位

这样我们把空位的值设为$1$,有人设置为$0$

那么倒序每次查找第$x+1$个空位就好了嘛~

这样直接上线段树也很简单了(权值线段树)

如果去掉头文件等只有20行

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn=8e5+10;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
int n,k,a[maxn],num[maxn],x[maxn],f[maxn],casenum;
void build(int rt,int l,int r)
{if( l==r ){ a[rt]=1; return; }build(lson); build(rson);a[rt] = a[ls]+a[rs];
}
void insert(int rt,int l,int r,int u,int val)//u是位置,val是编号 
{if( l==r ){  a[rt]=0;num[l]=val; return; }if( a[ls]>=u )	insert(lson,u,val);else	insert( rson,u-a[ls],val );a[rt] = a[ls]+a[rs];
}
int main()
{while( cin >> n ){for(int i=1;i<=n;i++)	scanf("%d%d",&x[i],&f[i]);build(1,1,n);for(int i=n;i>=1;i--)	insert(1,1,n,x[i]+1,f[i] );for(int i=1;i<=n;i++)	printf("%d ",num[i] );printf("\n");}
}