https://www.luogu.com.cn/problem/AT_abc388_d
第 i 个人成年后一共需要给 n-i 个石头，当然如果不够越后面成年的就分不到石头。
我们用线段树维护。
到这个人成年后，以后还要分 n-i 个石头，如果不够那就变成 0 ，然后分了几个石头，就然后面若干个人的石头加 1 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int n,a[N];
int tree[N],tag[N];
void lazy(int l,int r,int now,int k)
{
tree[now]+=k*(r-l+1);
tag[now]+=k;
}
void push_up(int now)
{
tree[now]=tree[now*2]+tree[now*2+1];
}
void push_down(int l,int r,int now)
{
int mid=(l+r)/2;
lazy(l,mid,now*2,tag[now]);
lazy(mid+1,r,now*2+1,tag[now]);
tag[now]=0;
}
void build(int l,int r,int now)
{
if(l==r)
{
tree[now]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
push_up(now);
}
void update(int l,int r,int nl,int nr,int now,int k)
{
if(nl<=l&&r<=nr)
{
tree[now]+=(r-l+1)*k;
tag[now]+=k;
return;
}
push_down(l,r,now);
int mid=(l+r)/2;
if(mid>=nl) update(l,mid,nl,nr,now*2,k);
if(mid<nr) update(mid+1,r,nl,nr,now*2+1,k);
push_up(now);
}
int query(int l,int r,int nl,int nr,int now)
{
int ans=0;
if(nl<=l&&r<=nr) return tree[now];
push_down(l,r,now);
int mid=(l+r)/2;
if(mid>=nl) ans+=query(l,mid,nl,nr,now*2);
if(mid<nr) ans+=query(mid+1,r,nl,nr,now*2+1);
return ans;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
for(int i=1;i<=n;++i)
{
int t=min(query(1,n,i,i,1),n-i);//计算这个人以后要分几块石头。
update(1,n,i,i,1,-t);//既然分了自己就要减少
if(i+1<=n) update(1,n,i+1,i+t,1,1);//然后往后分
printf("%lld ",query(1,n,i,i,1));//分完就可以计算出答案了
}
return 0;
}
真服了对了4题等级分只加了41分，第四题至少绿呀
不定时发布题解、算法讲解
点赞加速更新