F. Non-equal Neighbours - 题解

比赛与标签

比赛: Codeforces Round 759 (Div. 2, based on Technocup 2022 Elimination Round 3) 标签: combinatorics, data structures, dp, math 难度: *2400

题目大意喵~

主人你好呀~！这道题目是这样的呐：

给定一个长度为 n 的正整数数组 a。我们需要找到有多少个同样长度为 n 的正整数数组 b，能够满足下面两个条件喵：

1. 对于所有的 i (从 1 到 n)，b[i] 的值必须在 1 和 a[i] 之间，也就是 1 <= b[i] <= a[i]。
2. 对于所有的 i (从 1 到 n-1)，相邻的两个元素不能相等，也就是 b[i] != b[i+1]。

因为答案可能会非常大，所以需要我们对 998244353 取模的说。

举个例子，如果 a = [2, 2, 2]，那么合法的 b 数组就有 [1, 2, 1] 和 [2, 1, 2] 这两种，所以答案就是 2 啦！

解题思路喵！

这道题看起来有点复杂，但别怕，我们一步一步来分析它，喵~ ✨

1. 动态规划的初步想法

看到这种计数问题，而且涉及到序列的构建，我们很自然地会想到动态规划（DP）的说。

我们可以尝试定义一个 DP 状态。一个简单的想法是，dp[i] 表示构造前 i 个元素 b[1...i] 的合法方案数。但是，b[i+1] 的取值范围不仅依赖于 a[i+1]，还依赖于 b[i] 的具体值。所以，只知道前 i 位的方案总数是不够的。

那么，我们把状态定义得更详细一点：dp[i][j] 表示构造了前 i 个元素，且 b[i] = j 的合法方案数。

这样，状态转移就很清晰了： dp[i][j] = sum(dp[i-1][k])，其中 1 <= k <= a[i-1] 且 k != j。

这个转移可以写成： dp[i][j] = (sum_{k=1}^{a_{i-1}} dp[i-1][k]) - dp[i-1][j]

我们记 F[i-1] = sum_{k=1}^{a_{i-1}} dp[i-1][k]，也就是构造前 i-1 位的所有合法方案总数。 那么转移方程就变成了： dp[i][j] = F[i-1] - dp[i-1][j]，这个式子在 1 <= j <= a[i] 的范围内成立。

我们要求的第 i 步的总方案数 F[i] 就是： F[i] = sum_{j=1}^{a_i} dp[i][j] = sum_{j=1}^{a_i} (F[i-1] - dp[i-1][j])F[i] = a[i] * F[i-1] - sum_{j=1}^{a_i} dp[i-1][j]

这个 DP 方程就是我们解题的核心啦！但是有一个大问题：a[i] 的值可以达到 10^9，我们不可能开一个这么大的数组来存 dp[i-1][j] 的值。怎么办呢？

2. 观察与优化：坐标离散化

虽然 a[i] 的值很大，但 n 的范围是 2 * 10^5，相对小很多。这意味着，影响我们计算的 a[i] 的取值点其实并不多。

我们来观察一下 dp[i-1][j] 这个函数（把它看作关于 j 的函数）。

• 当 i=1 时，dp[0][j] = 1 对于 1 <= j <= a[0]。这是一个分段常数函数。
• 当 i=2 时，dp[1][j] = F[0] - dp[0][j]。对于 1 <= j <= a[0]，dp[1][j] = F[0] - 1。对于 a[0] < j <= a[1]，dp[0][j] 是 0，所以 dp[1][j] = F[0]。这仍然是一个分段常数函数！

我们发现，在每一步 i，dp[i-1][j] 的值在某些区间内是恒定的。这些区间的端点，只可能是 1 和 a[k]+1 (对于 k < i-1)。

所以，我们可以把所有 a[i] 和 a[i]+1 作为“断点”，对坐标轴进行离散化！我们将这些点排序、去重，形成一系列的互不相交的左闭右开区间 [p_k, p_{k+1})。在每个这样的小区间内，dp[i-1][j] 的值都是一个常数。

3. 线段树 + 懒标记闪亮登场！

既然是区间操作，那当然是我们最喜欢的线段树啦，喵~！

我们可以用线段树来维护 dp 值。线段树的每个叶子节点对应一个离散化后的基本区间。节点上需要维护这个区间内 dp 值的总和。

在计算 F[i] 时，我们需要：

1. 查询：计算 sum_{j=1}^{a_i} dp[i-1][j]。这对应在线段树上的一次区间查询。
2. 更新：计算出 F[i] 后，我们需要更新 dp 数组为 dp[i][j]，以备下一步计算使用。
   • 对于 1 <= j <= a[i]，dp 值从 v 变为 F[i-1] - v。
   • 对于 j > a[i]，dp 值变为 0。

这个更新操作 v -> C - v 可以分解成：先将 v 乘以 -1，再加上一个常数 C。这是一种线性变换 v -> m*v + a。 所以，我们需要一个支持区间乘法和区间加法的线段树。这就需要用到懒标记 (Lazy Propagation) 啦！

每个线段树节点需要维护两个懒标记：

• lazy_m: 乘法标记
• lazy_a: 加法标记

当一个更新 (m', a') 到达一个已经有懒标记 (m, a) 的节点时，新的值 v_new 会是 (v_old * m + a) * m' + a' = v_old * (m * m') + (a * m' + a')。 所以，懒标记的合并规则是：

• new_lazy_m = old_lazy_m * m'
• new_lazy_a = old_lazy_a * m' + a'

4. 算法流程总结

好啦，把所有东西串起来，我们的算法就成型了！

1. 离散化：收集所有的 a[i] 和 a[i]+1，以及 0, 1 等边界值，排序去重，得到离散化的端点 points。
2. 建树：根据 points 数组构建线段树。每个叶子节点 k 存储对应区间 [points[k], points[k+1]-1] 的长度。初始时所有 dp 值为 0。
3. 初始化 (i=0)：
   • dp[0][j] = 1 for 1 <= j <= a[0]。
   • 在线段树上找到 [1, a[0]] 对应的区间范围，进行区间更新：乘以 0，加上 1。
   • F[0] = a[0] % MOD。
4. 循环 (i=1 to n-1)：
   • 查询：在线段树上查询 [1, a[i]] 区间内 dp[i-1][j] 的总和，记为 S。
   • 计算：F[i] = (a[i] * F[i-1] - S) % MOD。（注意处理负数）
   • 更新：
     • 对 [1, a[i]] 对应的区间，进行更新 v -> F[i-1] - v。懒标记为 (m=-1, a=F[i-1])。
     • 对 [a[i]+1, max_val] 对应的区间，进行更新 v -> 0。懒标记为 (m=0, a=0)。
   • 将 F[i] 作为下一次迭代的 F_prev。
5. 输出：最终的答案就是 F[n-1]。

这样，我们就能在 O(n log n) 的时间内解决这个问题啦！是不是很酷？喵~

代码实现的说

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

const int MOD = 998244353;
const int MAX_INTERVALS = 600000; // 离散化后区间的最大数量，2*n 级别

// --- 全局变量定义 ---
vector<long long> points; // 存储离散化的坐标点
vector<long long> arr;
int n;

// --- 线段树数组 ---
long long tree[4*MAX_INTERVALS];      // 存储区间dp值的和
long long lazy_m[4*MAX_INTERVALS]; // 乘法懒标记
long long lazy_a[4*MAX_INTERVALS]; // 加法懒标记
long long seg_len[4*MAX_INTERVALS];  // 存储每个线段树节点代表的区间总长度

// 构建线段树
void build(int v, int l, int r, vector<long long>& len_arr) {
    lazy_m[v] = 1; // 乘法标记初始化为1
    lazy_a[v] = 0; // 加法标记初始化为0
    if (l == r) {
        tree[v] = 0; // 初始dp值为0
        seg_len[v] = len_arr[l] % MOD; // 叶子节点长度
    } else {
        int mid = (l+r)/2;
        build(2*v, l, mid, len_arr);
        build(2*v+1, mid+1, r, len_arr);
        tree[v] = (tree[2*v] + tree[2*v+1]) % MOD;
        seg_len[v] = (seg_len[2*v] + seg_len[2*v+1]) % MOD;
    }
}

// 将懒标记应用到当前节点
void apply(int v, long long m_val, long long a_val) {
    // tree_new = tree_old * m_val + a_val * len
    tree[v] = (tree[v] * m_val + a_val * seg_len[v]) % MOD;
    if (tree[v] < 0) tree[v] += MOD;
    
    // lazy_new = (lazy_old * m_val) + a_val
    lazy_m[v] = (lazy_m[v] * m_val) % MOD;
    lazy_a[v] = (lazy_a[v] * m_val + a_val) % MOD;
    if (lazy_a[v] < 0) lazy_a[v] += MOD;
}

// 下推懒标记
void push(int v) {
    if (lazy_m[v] != 1 || lazy_a[v] != 0) {
        apply(2*v, lazy_m[v], lazy_a[v]);
        apply(2*v+1, lazy_m[v], lazy_a[v]);
        lazy_m[v] = 1; // 重置当前节点懒标记
        lazy_a[v] = 0;
    }
}

// 区间更新: 对[ql, qr]范围内的值进行 v -> v * m_val + a_val 的变换
void update_range(int v, int l, int r, int ql, int qr, long long m_val, long long a_val) {
    if (ql > qr) return;
    if (qr < l || ql > r) return;
    if (ql <= l && r <= qr) {
        apply(v, m_val, a_val);
        return;
    }
    push(v);
    int mid = (l+r)/2;
    if (ql <= mid) {
        update_range(2*v, l, mid, ql, qr, m_val, a_val);
    }
    if (qr > mid) {
        update_range(2*v+1, mid+1, r, ql, qr, m_val, a_val);
    }
    tree[v] = (tree[2*v] + tree[2*v+1]) % MOD;
    if (tree[v] < 0) tree[v] += MOD;
}

// 区间查询: 查询[ql, qr]范围内的dp值总和
long long query_range(int v, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) {
        return tree[v];
    }
    push(v);
    int mid = (l+r)/2;
    long long res = 0;
    if (ql <= mid) {
        res = (res + query_range(2*v, l, mid, ql, qr)) % MOD;
    }
    if (qr > mid) {
        res = (res + query_range(2*v+1, mid+1, r, ql, qr)) % MOD;
    }
    if (res < 0) res += MOD;
    return res;
}

// 找到值x对应的离散化区间的索引
int find_index(long long x) {
    // upper_bound找到第一个大于x的元素
    // 我们需要的是包含x的区间 [points[idx], points[idx+1]), 所以找第一个大于x的然后-1
    auto it = upper_bound(points.begin(), points.end(), x);
    if (it == points.begin()) {
        return -1;
    }
    it--;
    int idx = it - points.begin();
    return idx;
}

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

    cin >> n;
    arr.resize(n);
    for (int i=0; i<n; i++) {
        cin >> arr[i];
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // --- 1. 坐标离散化 ---
    points = {0, 1}; // 0和1是重要的边界
    long long max_val = 0;
    for (int i=0; i<n; i++) {
        points.push_back(arr[i]);
        points.push_back(arr[i]+1); // a[i]和a[i]+1都是重要的断点
        if (arr[i] > max_val) max_val = arr[i];
    }
    points.push_back(max_val+2); // 确保有一个上界
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());

    int M = points.size();
    int num_intervals = M-1;

    vector<long long> len_arr(num_intervals);
    for (int i=0; i<num_intervals; i++) {
        len_arr[i] = points[i+1] - points[i];
    }

    // --- 2. 构建线段树 ---
    build(1, 0, num_intervals-1, len_arr);

    // --- 3. 初始化 (i=0) ---
    // dp[0][j] = 1 for 1 <= j <= a[0]
    int i_l0 = find_index(1);
    int i_r0 = find_index(arr[0]);
    if (i_l0 > i_r0) { i_r0 = i_l0; } // 处理 a[0] < 1 的情况（虽然题目保证正整数）
    update_range(1, 0, num_intervals-1, i_l0, i_r0, 0, 1); // 区间更新: v -> v*0 + 1 = 1

    long long F_prev = arr[0] % MOD; // F[0] = a[0]

    if (n == 1) {
        cout << F_prev << endl;
        return 0;
    }

    // --- 4. DP循环 ---
    for (int i=1; i<n; i++) {
        int i_l = find_index(1);
        int i_r = find_index(arr[i]);
        if (i_l > i_r) { i_r = i_l; }

        // 查询 sum(dp[i-1][j]) for 1 <= j <= a[i]
        long long S = query_range(1, 0, num_intervals-1, i_l, i_r);
        S = (S % MOD + MOD) % MOD;
        
        // 计算 F[i]
        long long F_cur = ( ( (arr[i] % MOD) * F_prev ) % MOD - S ) % MOD;
        if (F_cur < 0) F_cur += MOD;

        // 更新dp数组为dp[i]
        // For 1 <= j <= a[i], dp[i][j] = F_prev - dp[i-1][j]
        // 对应变换 v -> F_prev - v, 即 v -> v*(-1) + F_prev
        update_range(1, 0, num_intervals-1, i_l, i_r, MOD-1, F_prev);

        // For j > a[i], dp[i][j] = 0
        // 对应变换 v -> 0, 即 v -> v*0 + 0
        int next_interval = i_r+1;
        if (next_interval <= num_intervals-1) {
            update_range(1, 0, num_intervals-1, next_interval, num_intervals-1, 0, 0);
        }
        
        F_prev = F_cur; // 为下一次迭代做准备
    }

    cout << F_prev << endl;
    return 0;
}

复杂度分析呐

• 时间复杂度: O(n log n) 的说。

  • 坐标离散化需要收集 O(n) 个点，排序它们需要 O(n log n) 的时间。
  • 主循环执行 n-1 次。
  • 在每次循环中，我们执行常数次线段树的查询和更新操作。离散化后，线段树的大小是 O(n)，所以每次操作的复杂度是 O(log n)。
  • 因此，总的时间复杂度由排序和DP循环主导，为 O(n log n)。

• 空间复杂度: O(n) 的说。

  • points 数组存储离散化的点，大小为 O(n)。
  • 线段树的数组 tree, lazy_m, lazy_a, seg_len 都需要 4 * O(n) 的空间，所以是 O(n)。
  • 其他变量都是常数或 O(n) 大小。

知识点与总结喵~

这道题是一道非常经典的 DP + 数据结构优化问题，融合了多种技巧，做出来会很有成就感哦！

1. 核心思想: 动态规划 (DP) 是解题的基石。我们从最基本的 dp[i][j] 状态出发，推导出 F[i] = a[i] * F[i-1] - sum(dp[i-1][j]) 这个关键的递推关系。

2. 优化技巧: 坐标离散化 (Coordinate Discretization) 是处理大坐标范围问题的利器。当问题的关键点数量远小于坐标范围时，离散化能有效地将问题规模降下来。

3. 数据结构: 带懒标记的线段树 (Segment Tree with Lazy Propagation) 是本题的执行核心。特别地，这里我们需要一个能处理区间线性变换（即区间乘法和区间加法）的强大线段树。理解懒标记如何合并（new_lazy = old_lazy * m' + a'）是实现的关键。

4. 编程技巧:

   • 处理模运算时要非常小心，特别是减法可能导致负数，需要 (x % MOD + MOD) % MOD 来保证结果非负。
   • upper_bound 是在离散化坐标中快速定位的好帮手。

总的来说，解决这道题需要我们将DP的数学推导能力和对高级数据结构的熟练运用结合起来。只要一步步拆解问题，再可怕的题目也能被我们征服的！加油，主人！你超棒的！喵~ (ฅ'ω'ฅ)