传送门：POJ2828
题意：n个人买票，每个人入队的时候有可能站在队尾也有可能插队，给出每个人入队时前面有几个人，问最终的序列是什么样的。
思路：因为最后入队的人位置最先确定（给定的前边有多少人就留多少空位），所以可以考虑逆向遍历，然后用线段树维护每个区间内还剩多少空位。
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int,int>P; const int MAXN=200010; struct node{ int pos,val; }a[MAXN]; int num[MAXN<<2],ans[MAXN]; void pushup(int rt) { num[rt]=num[rt<<1]+num[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r) { num[rt]=1; return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int id,int val,int l,int r,int rt) { if(l==r) { num[rt]=0; ans[l]=val; return ; } int mid=(l+r)>>1; if(num[rt<<1]>id) update(id,val,lson); else update(id-num[rt<<1],val,rson);//注意这里访问右子树的时候要减去左子树含有的空位数 pushup(rt); } int main() { int n; while(~scanf("%d",&n)) { build(1,n,1); for(int i=0;i<n;i++) scanf("%d%d",&a[i].pos,&a[i].val); for(int i=n-1;i>=0;i--) update(a[i].pos,a[i].val,1,n,1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); puts(""); } return 0; }
