Alice likes snow a lot! Unfortunately, this year's winter is already over, and she can't expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amount of snow every day. On day i he will make a pile of snow of volume Vi and put it in her garden.
Each day, every pile will shrink a little due to melting. More precisely, when the temperature on a given day is Ti, each pile will reduce its volume by Ti. If this would reduce the volume of a pile to or below zero, it disappears forever. All snow piles are independent of each other.
Note that the pile made on day i already loses part of its volume on the same day. In an extreme case, this may mean that there are no piles left at the end of a particular day.
You are given the initial pile sizes and the temperature on each day. Determine the total volume of snow melted on each day.
Output
Output a single line with N integers, where the i-th integer represents the total volume of snow melted on day i.
Note
In the first sample, Bob first makes a snow pile of volume 10, which melts to the size of 5 on the same day. On the second day, he makes another pile of size 10. Since it is a bit warmer than the day before, the first pile disappears completely while the second pile shrinks to 3. At the end of the second day, he has only a single pile of size 3. On the third day he makes a smaller pile than usual, but as the temperature dropped too, both piles survive till the end of the day.
算出第i堆学在第j天全部消融，算出第i堆雪在j天的消融量。再用线段树维护从第i天道第j-1天的消融量
#include
#define ll long long
#define maxn 100010
using namespace std;
ll A[maxn<<2];
ll a[maxn],b[maxn],c[maxn];
void update(int k,int L,int R,int l,int r)
{
if(rmid)
update(2*k+1,mid+1,R,l,r);
else
{
update(2*k,L,mid,l,mid);
update(2*k+1,mid+1,R,mid+1,r);
}
}
ll query(int k,int L,int R,int t)
{
if(L==R)
return A[k];
ll mid=(L+R)/2;
if(t<=mid)
return query(2*k,L,mid,t)+A[k];
else
return query(2*k+1,mid+1,R,t)+A[k];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
b[i]=b[i-1]+t;
}
for(int i=1;i<=n;i++)
{
a[i]+=b[i-1];//先把i天之前的温度加上
ll j=1ll*(lower_bound(b+i,b+n+1,a[i])-b);//找到第i堆雪存在的天数
c[j]+=a[i]-b[j-1];//计算出第j天第i堆雪的消融量
update(1,1,n,i,j-1);//线段树维护第i天到第j-1天雪量大于等于温度的雪堆数目
}
for(int i=1;i<=n;i++)
{
c[i]+=query(1,1,n,i)*(b[i]-b[i-1]);
printf("%lld ",c[i]);
}
return 0;
}
京公网安备 11010802041100号