Buy Tickets

描述

有n个人，给出每个人在第几个位置之后，和权值，最后输出队伍。

思路

很明显的是正序做很不容易找到位置，而且会变换位置，但如果倒序做的话，该点在哪个位置就是哪个位置，不会在改变，如果要加入一个点，并且该点是在k后面的话，那么从左端点向右找够k+1个格；

代码

#include <iostream> #include <cstdio> #include <cstring> #define ROOT 1,1,n #define LSON root<<1,l,mid #define RSON root<<1|1,mid+1,r using namespace std; typedef long long ll; const int maxn=200000+10; int n; int sum[maxn]; int a[maxn],data[maxn]; struct node { int sum,data; }T[maxn*4]; void build(int root,int l,int r); void update(int root) { T[root].sum=T[root<<1].sum+T[root<<1|1].sum; } void insert1(int root,int l,int r,int len,int k); void print(int root,int l,int r); int main() { freopen("test.in","r",stdin); freopen("test.out","w",stdout); while((scanf("%d",&n))==1) { memset(T,0,sizeof(T)); memset(sum,0,sizeof(sum)); for(int i=1; i<=n; i++) { scanf("%d %d",&a[i],&data[i]); } build(ROOT); for(int i=n; i>=1; i--) insert1(ROOT,a[i]+1,data[i]); print(ROOT); puts(""); } return 0; } void build(int root,int l,int r) { if(l==r) { T[root].sum=1; return; } else { int mid=(l+r)>>1; build(LSON); build(RSON); update(root); } } void insert1(int root,int l,int r,int len,int k) { int mid=(l+r)>>1; if(l==r) { T[root].sum=0; T[root].data=k; } else { if(T[root<<1].sum>=len) insert1(LSON,len,k); else { insert1(RSON,len-T[root<<1].sum,k); } update(root); } } void print(int root,int l,int r) { if(l==r) { printf("%d ",T[root].data); return; } else { int mid=(l+r)>>1; print(LSON); print(RSON); return; } }