题解：2024牛客暑期多校第1场——C [Sum of Suffix Sums]

英文题干

Given an array which is initially empty, you need to perform 𝑞 operations: Given two non-negative integers 𝑡 and 𝑣, take out the element from the end of the array for 𝑡 times and then append 𝑣 to the end of the array. It is guaranteed that 𝑡 does not exceed the length of the array before this operation.

After each operation, let $a_1,a_2,..,a_n$ be the current array, find the sum of $s_1,s_n,...,s_n$ , where $s_i=a_i a_{i 1} ... a_n$ is the sum of the suffix starting from position 𝑖.

Since the answers may be very large, output them modulo 1000000007.

Input:

The first line contains an integer $q (1\leq q\leq 5\times 10^5)$ , denoting the number of operations.

Each of the following 𝑞 lines contains two non-negative integers 𝑡 and 𝑣 ( $0\leq v\leq 10^9$ ), describing an operation, where 𝑡 does not exceed the length of the array before this operation.

Output:

Output 𝑞 lines, each of which contains an integer, denoting the answer.

中文题干

给定一个最初为空的数组，您需要执行 𝑞 次操作：给定两个非负整数 𝑡 和 𝑣，从数组末尾取出元素 𝑡 次，然后将 𝑣 追加到数组末尾。保证在此操作之前，数组的长度不超过 𝑡。

每次操作后，假设 $a_1,a_2,..,a_n$ 是当前数组，找到 $s_1,s_n,...,s_n$ 的和，其中 $s_i=a_i a_{i 1} ... a_n$ 是从位置 𝑖 开始的后缀的总和。

由于答案可能很大，对结果取模 1000000007。

思路

一道线性dp签到题

首先可以利用vector的erase方法删去末尾元素
然后将v的p倍（p为数组长度+1）追加到vector末尾以实现后缀和的计算。同时用b[i]维护每次求得的后缀和，以供减少后续的重复计算。

AC代码

时间复杂度：O( $n\times t$ )


#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;

vector<ll> a; // 存储操作后的数组
ll b[maxn];   // 存储后缀和的数组

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t;
        ll v;
        cin >> t >> v;

        a.erase(a.end() - t, a.end()); // 删除数组末尾的 t 个元素

        ll p = a.size() + 1;
        a.push_back(v * p);                    // 将 v*p 加入数组末尾
        b[p] = b[p - 1] % mod + (v * p) % mod; // 更新后缀和数组 b

        cout << b[p] % mod << endl; // 输出当前后缀和的总和并取模
    }
}
// Inspired by LJY