题解：AT_abc457_f [ABC457F] Second Gap / ARIS0_0 - 37

· · 题解

前言

我他妈为什么没有 AK 这场简单的比赛。

思路

我们天真的考虑直接把最大值和最小值直接塞到 dp 状态里面，然后我们的 dp 雏形是这样的：dp_{i, fir, sec} 表示考虑 1 \sim i，最大值在下标 fir 处，次大在 sec 处，满足 1 \sim i 的所有条件的数量。

不过这确实很天真，毕竟你的最大和次大是从后面来的，你这个 1 \sim i 纯搞笑啊，所以变成 i \sim n，然后就，套路的，考虑 i 插入 i + 1 \sim n。

不难发现，f_{i + 1, a, b} 可以转移到 f_{i, a, i}，f_{i, i, a}，f_{i, a, b}。

先不谈怎么转移，你发现这个状态数量有点多，考虑通过这个转移方式去减少一些状态。发现，出现第三种情况当且仅当 D_i = D_{i + 1}。

于是，你发现，b 这个玩意被扔了。

这样子初始化就是直接 f_{n - 1, n - 1} = f_{n - 1, n} = 1，那就转移呗：

第一步，如果 D_i = D_{i + 1}，f_{i, j} = f_{i + 1, j} \times (n - i - 1)，其中 n - i - 1 的含义是，你要把 i 插入 n - i 个数字，并且不能插入到最大和第二大之前，一共有 n - i - 1 种方案。、

否则如果 D_i \neq D_{i + 1}，直接全部赋值为 0 即可。

第二部，将 f_{i, i} \leftarrow f_{i, i} + f_{i + 1, i + D_i}，f_{i, i + D_i} \leftarrow f_{i, i + D_i} + f_{i +1, i + D_i}。

这一步是显然的，就是如果你替换了最大值或是次大值，那么最大值是原本的最大值位置或是你本身，不难发现，如果要用你替换最大和次大之一，原本的最大值一定在 i + D_i 位置，所以转移正确。

最后的答案就是所有的 dp_{1, i} 之和。

然后，你考虑上面这个“单点加，区间乘，区间或单点查询和”，好像就是一个线段树板子。

然后注意取模你就做完了。

code

语言可能比较混乱，所以代码罕见的加了注释！

:::success[code]

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

#define int long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e18, mod = 998244353; // 注意模数

namespace ARIS0_0{
    int n, d[N];

    struct segment{
        int tr[N << 2], mul[N << 2]; // 四倍空间，以及乘法 lazy tag
        void addmul(int now, int x){
            tr[now] = 1ll * tr[now] * x % mod, mul[now] = 1ll * mul[now] * x % mod;
            // 下放 lazy tag，记得取模
        }
        void pushup(int now){
            tr[now] = (tr[now << 1] + tr[now << 1 | 1]) % mod;
            // 维护区间和
        }
        void pushdown(int now){
            if (mul[now] == 1) return ;
            addmul(now << 1, mul[now]);
            addmul(now << 1 | 1, mul[now]);
            mul[now] = 1;
        }
        void modify_add(int now, int l, int r, int pos, int x){ // 单点加
            if (l == r){
                tr[now] = (tr[now] + x) % mod; // 取模
                return ;
            }
            pushdown(now); // 下放 lazy tag
            int mid = (l + r) >> 1;
            if (pos <= mid) modify_add(now << 1, l, mid, pos, x); // to left
            else modify_add(now << 1 | 1, mid + 1, r, pos, x); // to right
            pushup(now); // 下方 lazy tag
        }
        int query(int now, int l, int r, int pos){ // 基础的线段树查询
            if (l == r) return tr[now];
            pushdown(now);
            int mid = (l + r) >> 1;
            if (pos <= mid) return query(now << 1, l, mid, pos); // to left
            return query(now << 1 | 1, mid + 1, r, pos); // to right
        }
    } seg;

    void init(){
    }
    void solve(){
        cin >> n;
        for (int i = 1; i < n; i ++ ) cin >> d[i]; // 读入

        for (int i = 1; i <= n + n + n + n; i ++ ) seg.mul[i] = 1, seg.tr[i] = 0; // 记得初始化

        seg.modify_add(1, 1, n, n, 1), seg.modify_add(1, 1, n, n - 1, 1); // dp[n - 1][n] = dp[n - 1][n - 1] = 1 对应的线段树操作。
        for (int i = n - 2; i >= 1; i -- ){
            // d[i] = d[i + 1] -> dp[i][any] = dp[i + 1][any] * (n - i - 1)
            // dp[i][i], dp[i][i + d[i]] add dp[i + 1][i + d[i]]
            int tmp = seg.query(1, 1, n, i + d[i]); // 注意要在下面的操作之前查询
            if (d[i] == d[i + 1]) seg.addmul(1, n - i - 1); // d[i] = d[i + 1] 的特殊情况
            else seg.addmul(1, 0); // 技巧：清空就是乘 0
            seg.modify_add(1, 1, n, i, tmp), seg.modify_add(1, 1, n, i + d[i], tmp); // i覆盖了最大值或者次大值
        }
        cout << seg.tr[1] << "\n"; // 技巧：全部和，直接拿 1
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::single();
}
// 你听啊冬至的白雪，你听它掩饰着哽咽，在没有你的世界，再没有你的冬眠
// ARIS0_0 - 37

:::