题目描述

难度分:$1600$

输入$n(1 \leq n \leq 10^5)$，长为$n$的数组$a(0 \leq a[i] \leq 10^9)$，长为$n$的数组$t(0 \leq t[i] \leq 10^9)$。

下雪啦！0x3F每天都要堆一个雪人，第$i$天0x3F会堆一个体积为$a[i]$的雪人。

• 第$i$天的温度是$t[i]$，体积为$x$的雪人在这天会融化掉$min(t[i], x)$的体积。

• 第$i$天新堆的雪人和之前堆的雪人都会融化。

对于每一天，输出这一天所有雪人融化掉的体积之和。

输入样例$1$

3
10 10 5
5 7 2

输出样例$1$

5 12 4

输入样例$2$

5
30 25 20 15 10
9 10 12 4 13

输出样例$2$

9 20 35 11 25

算法

贡献法

正着思考想了挺长时间，但是一直没想到“怎么在第$i$天高效动态维护$[1,i]$中体积小于$t[i]$的雪人数量和大于等于$t[i]$的雪人数量”。

所以就反向思考贡献了，对于第$i$天堆的雪人，我们思考它会在哪一段区间$[i,j]$融化。可以很容易发现，第$i$天雪人融化的日子$[i,j]$应该满足$\Sigma_{k=i}^{j}t[k] \geq a[i]$，由于$t$中都是非负数，所以先对$t$预处理出一个前缀和数组$s$。对于每个$i$，二分查找出满足$s[j]-s[i-1] \geq a[i]$的最左$j$。

1. 如果没有找到合法的$j$，说明后缀和$\Sigma_{k=i}^{n}t[k] \lt a[i]$，也就是后面每天$k \in [i,n]$都会在第$i$个雪人上融化$t[k]$的体积，可以在区间$[i,n]$上加$1$（利用差分数组$diff$来操作），这是雪人$i$对第$k$天的贡献。
2. 否则，当$s[j]-s[i-1] \gt a[i]$时，第$i$个雪人会在第$k \in [i,j)$天融化$t[k]$的体积，最后一天$j$，融化$a[i]-(s[j-1]-s[i-1])$，先把第$j$天的答案$ans[j]$加上$a[i]-(s[j-1]-s[i-1])$。当$s[j]-s[i-1]=a[i]$时，第$i$个雪人会在第$k \in [i,j]$天融化$t[k]$的体积。

最后遍历$i \in [1,n]$，一边计算$diff$数组的前缀和，一边计算每天的答案。第$i$天的答案应该还要加上$t[i] \times \Sigma_{k=1}^{i}diff[k]$，其中$\Sigma_{k=1}^{i}diff[k]$表示融化$t[i]$体积的次数。

复杂度分析

时间复杂度

瓶颈在于计算第$i$个雪人融化的时间区间需要进行$O(log_2n)$的二分查找，要计算$n$天，所以总的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于$t$的前缀和数组$s$，以及辅助进行区间加的差分数组$diff$，空间都是线性的。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, a[N], t[N];
LL s[N], diff[N], ans[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
        s[i] = s[i - 1] + t[i];
    }
    for(int i = 1; i <= n; i++) {
        int l = i, r = n, j = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(s[mid] - s[i - 1] >= a[i]) {
                j = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        // a[i]在日期[i,j]内都会融化
        if(j) {
            if(s[j] - s[i - 1] > a[i]) {
                if(i <= j) {
                    ans[j] += a[i] - (s[j - 1] - s[i - 1]);
                }
                diff[i]++;
                diff[j]--;
            }else {
                diff[i]++;
                diff[j + 1]--;
            }
        }else {
            diff[i]++;
            diff[n + 1]++;
        }
    }
    for(int i = 1; i <= n; i++) {
        diff[i] += diff[i - 1];
        ans[i] += diff[i]*t[i];
        printf("%lld ", ans[i]);
    }
    return 0;
}