POJ 2828 Buy Tickets
线段树的题总是这么火。。。
这题很多人都说想法很精妙啊，，赞一个。
说有n个人插队，给定插队的先后顺序和插在哪个位置还有每个人的val，求插队结束后队伍各位置的val。
一般来说插入这种事情都是倒着推的。
对于第i个人来说，他插队的时候前面已经站满了，那么他前面应该有pos个人。
但是i后面可能有人插到i前面，也就是说，倒着推的时候，i前面不只有pos个人，
但是可以说，i前面有pos个空位，这些空位是i之前的人站的位置。
于是可以用线段树维护一个序列，每个序列存放当前情况下，第j个位置之前有多少个空位，
那么对于i来说，找到j使得pos=g[j]，找的方法就是用线段树找，其实大致应该是二叉查找树的样子= =。
我的代码中维护的是包括第j个位置有多少个空位，所以找pos的时候pos+1
[cpp]
#include<stdio.h>
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define X 200010
int g[X*4],ll,rr,val;
int a[X],b[X],as[X];
void pushup(int rt){
g[rt]=g[rt*2]+g[rt*2+1];
}
void build(int l,int r,int rt){
if(l==r){g[rt]=1;return ;}
int mid=l+r>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int sum,int l,int r,int rt){
if(l==r){g[rt]=0;as[l]=val;return ;}
int mid=l+r>>1;
if(sum<=g[rt*2])update(sum,lson);
else update(sum-g[rt*2],rson);
pushup(rt);
}
int main(){
int i,j,n;
while(~scanf("%d",&n)){
build(1,X,1);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(i=n;i>0;i--){
val=b[i];
update(a[i]+1,1,X,1);
}
for(i=1;i<=n;i++)
printf("%d%c",as[i],i==n?'\n':' ');
}
return 0;
}
#include<stdio.h>
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define X 200010
int g[X*4],ll,rr,val;
int a[X],b[X],as[X];
void pushup(int rt){
g[rt]=g[rt*2]+g[rt*2+1];
}
void build(int l,int r,int rt){
if(l==r){g[rt]=1;return ;}
int mid=l+r>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int sum,int l,int r,int rt){
if(l==r){g[rt]=0;as[l]=val;return ;}
int mid=l+r>>1;
if(sum<=g[rt*2])update(sum,lson);
else update(sum-g[rt*2],rson);
pushup(rt);
}
int main(){
int i,j,n;
while(~scanf("%d",&n)){
build(1,X,1);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(i=n;i>0;i--){
val=b[i];
update(a[i]+1,1,X,1);
}
for(i=1;i<=n;i++)
printf("%d%c",as[i],i==n?'\n':' ');
}
return 0;
}
补充：软件开发 , C++ ,
