[CF1491C] Pekora and Trampoline

Description

有 \(n\) 个蹦床排成一列，每个蹦床有一个弹力值 \(s_i\)。每一轮的最开始，会任意选择一个蹦床作为她的起点。当她在蹦床 \(i\) 时，她会跳到蹦床 \(i+s_i\) 上，并且 \(s_i\) 会变为 \(\max(1,s_i-1)\)（也就是说，蹦床每被跳一次弹力值就会减一，直到弹力值为 \(1\)）。当她跳到了第 \(n\) 个蹦床的后面时，该轮结束。现在想要把所有的 \(s_i\) 都变成 \(1\)，问最少要多少轮才能实现这个目标。

Solution

从一个位置开始，会让后面的一些位置被经过若干次，因此我们可以从左往右扫一遍，每次遇到一个没处理完的，就必须从这里开始处理若干次，这样不会使得答案更劣

我们维护一个 \(t_i\) 表示第 i 个位置被前面的操作经过了多少次

那么很显然这个位置需要做 \(\max(S_i-t_i-1,0)\) 次

这个位置会导致后面的 \(i+2..i+S_i\) 被经过 1 次，导致 \(i+1\) 被经过 \(t_i-S_i+1\) 次

相当于我们要对 \(t[i+2..i+S_i]\) 加上 \(1\)，对 \(t[i+1]\) 加上 \(Clamp(t_i-S_i+1)\)

我们可以用差分标记来维护，每次对 \(c[i+2]+1, c[i+S_i+1]-1\)，对于 \(c[i+1]+Clamp(t_i-S_i+1)\)，对 \(c[i+2]-Clamp(t_i-S_i+1)\)

时间复杂度 O(n)

（验题时候题还是这个 O(n) 的版本，硬是没想到差分）

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

#define int long long

void solve()
{
    int n;
    cin >> n;

    vector<int> s(n + 2), c(n + 4);
    int t = 0, ans = 0;

    for (int i = 1; i <= n; i++)
        cin >> s[i];

    for (int i = 1; i <= n; i++)
    {
        t += c[i];
        c[i + 2]++;
        c[min(n + 1, i + s[i] + 1)]--;
        c[i + 1] += max(0ll, t - s[i] + 1);
        c[i + 2] -= max(0ll, t - s[i] + 1);
        ans += max(s[i] - t - 1, 0ll);
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
        solve();
}