Problem Statement

On a certain planet, there are $N$ aliens, all of whom are minors.

The $i$-th alien currently has $A_i$ stones, and will become an adult exactly $i$ years later.

When someone becomes an adult on this planet, every adult who has at least one stone gives exactly one stone as a congratulatory gift to the alien who has just become an adult.

Find how many stones each alien will have after $N$ years.

Assume that no new aliens will be born in the future.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq A_i \leq 5 \times 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

Output

Let $B_i$ be the number of stones owned by the $i$-th alien after $N$ years. Print $B_1, B_2, \ldots, B_N$ in this order, separated by spaces.

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
using namespace std;
const int Maxn = 5e5 + 10;
int a[Maxn],d[Maxn];//d为差分数组
//全局定义下数组自动初始化为0
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    int pre = 0;
    for(int i=1;i<=n;i++)
    {
        //pre代表起始位置到当前位置i累积起来的所有 “修正量”,即进行过几次差分操作，这也与前面一共有几个外星人能够发石头相互对应
        pre += d[i];
        //能有pre个人给第i个外星人发石头，加上得到第i个人最多能拿到的石头数量
        a[i] += pre;
        //minus代表了第i个外星人需要发出去的石头数量,当这个人后面人数大于a[i]时a[i]-a[i]=0,小于a[i]时减去n-i
        int minus = min(n-i,a[i]);
        //常规差分操作
        a[i] -= minus;
        d[i+1] += 1;//注意是第i+1个外星人开始获得石头
        d[i+minus+1] -= 1;
    }
    for(int i=1;i<=n;i++) cout << a[i] << ' ';
    return 0;
}