POJ 2828 Buy Tickets | 线段树的喵用

题意:

给你n次插队操作,每次两个数,pos,w,意为在pos后插入一个权值为w的数;

最后输出1~n的权值

---

题解:

首先可以发现,最后一次插入的位置是准确的位置

所以这个就变成了若干个子问题,

所以用线段树维护一下每个区间剩余多少位置可选

对于一个pos

如果左儿子的剩余超过当前位置,就递归进左子树

反之就相当于留出了左儿子剩余的位置,递归进右子树,当前位置变成pos-左儿子剩余位置

请注意是在后面插入

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
#define N 200010
using namespace std;
struct node
{
    ll l,r,sum,w;
}t[4*N];
ll p[N],w[N];
ll read()
{
    ll ret=0,neg=1;
    char j=getchar();
    for (;j>'9' || j<'0';j=getchar())
    if (j=='-') neg=-1;
    for (;j<='9' && j>='0';j=getchar())
    ret=ret*10+j-'0';
    return ret*neg;
}
ll n,q,l,r,k,ans[N];
void pushup(ll p)
{
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
void build(ll p,ll l,ll r)
{
    t[p].l=l,t[p].r=r;
    if (l!=r)
    {
    ll mid=l+r>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    pushup(p);
    }
    else
    t[p].sum=1;
}
void modify(ll p,ll pos,ll k)
{
    if (t[p].l==t[p].r)
    {
    ans[t[p].l]=k;
    t[p].sum--;
    return ;
    }
    if (t[2*p].sum>=pos) modify(2*p,pos,k);
    else modify(2*p+1,pos-t[2*p].sum,k);
    pushup(p);
}
int main()
{
    while (scanf("%lld",&n)!=EOF)
    {
    build(1,1,n);
    for (int i=1;i<=n;i++)
        p[i]=read(),w[i]=read();
    for (int i=n;i>=1;i--)
        modify(1,p[i]+1,w[i]);
    for (int i=1;i<=n;i++)
        printf("%lld%c",ans[i]," \n"[i==n]);
    }
    return 0;
}