poj 2828 Buy Tickets 题解(插队问题+线段树上二分)

题目链接

题目大意

有(n(nle 2e5))个人来排队，第 (i)个人来的时候会排在第 (p[i](0 le p[i]< i))个人的后面，它会被分配一个数字

(v[i])。现在告诉你 (n)对((p[i], v[i]))，请你按照队伍顺序输出每个人的数字。

题目思路

首先思考下会发现正序根本不能下手，所以要倒序考虑

你如果从第(n)个人开始考虑，那么显然第(n)个人的位置是显而易见的，显然为(p[n]+1)

那么再考虑第(n-1)个人，在不考虑后面的人的情况下，那么答案就是(p[n-1]+1)

但是若是考虑后面的人且(p[n]+1)小于等于(p[n-1]+1)，答案则变为(p[n-1]+2)

那么你再以此类推思考思考，其实从后往前考虑的话

你只需要找到第(p[i]+1)个空位即可

为什么呢，因为后面的元素位置都已经确定了，都已经占了位置

而你就是放在没有确定的第(p[i])个位置后面

你可以用线段树维护区间([l,r])中空位的个数

那么一个很显然的想法就是二分套线段树来确定那个位置

但是你会发现其实线段树本身就是二分的分治,分支套分治，一般都会出现冗余

直接在线段树上二分即可

更新和查询一起操作，妙妙妙

代码

#include<cstdio>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
int ans[maxn];
int pos[maxn],val[maxn];
int tree[maxn<<2];
void change(int node,int l,int r,int pos,int val){
    //这里没有被建树，显然没有值
    if(l==r){
        tree[node]=0;
        ans[l]=val;
        return ;
    }
    int mid=(l+r)/2;
    if(tree[node<<1]>=pos) change(node<<1,l,mid,pos,val);
    else change(node<<1|1,mid+1,r,pos-tree[node<<1],val);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}
void build(int node,int l,int r){
    if(l==r){
        tree[node]=1;
        return ;
    }
    int mid=(l+r)/2;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}
signed main(){
    while(scanf("%d",&n)!=-1){
        build(1,1,n);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&pos[i],&val[i]);
        }
        for(int i=n;i>=1;i--){
            change(1,1,n,pos[i]+1,val[i]);
        }
        for(int i=1;i<=n;i++){
            printf("%d ",ans[i]);
        }
        printf("
");
    }
    return 0;
}