题意:
给你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[*N];
ll p[N],w[N];
ll read()
{
ll ret=,neg=;
char j=getchar();
for (;j>'' || j<'';j=getchar())
if (j=='-') neg=-;
for (;j<='' && j>='';j=getchar())
ret=ret*+j-'';
return ret*neg;
}
ll n,q,l,r,k,ans[N];
void pushup(ll p)
{
t[p].sum=t[*p].sum+t[*p+].sum;
}
void build(ll p,ll l,ll r)
{
t[p].l=l,t[p].r=r;
if (l!=r)
{
ll mid=l+r>>;
build(*p,l,mid);
build(*p+,mid+,r);
pushup(p);
}
else
t[p].sum=;
}
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[*p].sum>=pos) modify(*p,pos,k);
else modify(*p+,pos-t[*p].sum,k);
pushup(p);
}
int main()
{
while (scanf("%lld",&n)!=EOF)
{
build(,,n);
for (int i=;i<=n;i++)
p[i]=read(),w[i]=read();
for (int i=n;i>=;i--)
modify(,p[i]+,w[i]);
for (int i=;i<=n;i++)
printf("%lld%c",ans[i]," \n"[i==n]);
}
return ;
}