题目翻译

E. 另一种折叠纸条
每次测试的时间限制：2秒
每次测试的内存限制：256兆字节

对于一个长度为 $m$ 的数组 $b$，定义 $f(b)$ 如下：

考虑一个 $1 \times m$ 的纸条，初始时所有格子的暗度为 $0$。
你想把它变成第 $i$ 个位置的暗度为 $b_i$ 的纸条。
你可以进行如下操作，每次操作包含两步：

1. 在任意两个格子之间的线处折叠纸条。你可以折叠任意多次，也可以不折叠。
2. 选择一个位置滴下黑色染料。染料从顶部渗透到底部，使其路径上的所有格子的暗度增加 $1$。滴完染料后，你将纸条展开。

设 $f(b)$ 为达到目标配置所需的最少操作次数。可以证明，目标总是可以在有限次操作内实现。

现在给你一个长度为 $n$ 的数组 $a$。计算

$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(a_l a_{l+1} \dots a_r) $$

并对 $998244353$ 取模。

---

题目理解与题解

1. 操作的本质理解

这个操作非常巧妙。让我们理解一下：

• 折叠：可以在任意位置折叠纸条，可以多次折叠。折叠后，纸条的某些格子会重叠在一起。
• 滴染料：选择一个位置滴染料，染料会向下渗透，增加当前可见的所有重叠格子的暗度。
• 展开：展开后，每个格子得到它被折叠时所在位置的所有染料贡献。

关键观察：一次操作相当于选择一组位置（在折叠后重叠在一起的位置），给这些位置都加上 $1$。

2. 折叠的数学本质

如果我们把折叠看作是对纸条进行某种"折叠映射"，那么一次操作就是：

• 选择一个折叠方案（即选择一种将 $[1,m]$ 映射到某个更小区间的方式）
• 在映射后的某个位置滴染料，相当于给映射到该位置的所有原位置都 $+1$

经过多次操作，每个位置 $i$ 的最终暗度等于：有多少次操作中，位置 $i$ 被映射到了滴染料的位置。

3. 关键结论

结论1：对于任意数组 $b$，$f(b)$ 等于 $b$ 中所有正数的和？不对，因为一次操作可以给多个位置加 $1$。

结论2：实际上，这个问题等价于：每次操作可以选择一个"对称区间"（关于折叠中心对称的区间）并给其中的所有位置加 $1$。但折叠可以多层，所以更准确地说：

一次操作可以给任意一组满足某种对称性的位置加 $1$。经过分析，这个问题的经典结论是：

$f(b)$ 等于 $b$ 中所有正数的和减去可以"配对"消除的部分。更精确地说，$f(b) = \max(b)$？也不对。

让我们重新思考：考虑最简单的情况：

• 如果 $b = [0]$，$f(b) = 0$
• 如果 $b = [1]$，$f(b) = 1$
• 如果 $b = [0,1,0]$，$f(b) = 1$（可以折叠中间，滴一次染料）
• 如果 $b = [1,0,1]$，$f(b) = 1$（折叠两端重叠，滴一次）

4. 正确的理解

实际上，这个问题是 Codeforces 上的一个经典问题。经过推导，核心结论是：

$f(b)$ 等于将 $b$ 中所有相邻的相同数字配对后，剩余数字的个数。

但更准确地说：考虑将数组 $b$ 看作一个序列，每次操作可以：

• 选择一个中心点
• 给所有关于该中心对称的位置加 $1$

这意味着：如果两个位置在多次折叠后能重叠，那么它们必须是关于某个中心对称的。

经过深入分析，这个问题的标准解法是：

$f(b)$ 等于 $b$ 中所有正数的最大值？ 让我们验证：

• $[0,1,0]$：最大值 $1$，$f=1$ ✓
• $[1,0,0,1,2,1]$：最大值 $2$，但示例说 $f=2$ ✓
• $[1]$：最大值 $1$，$f=1$ ✓
• $[0]$：最大值 $0$，$f=0$ ✓

但考虑 $[1,1]$：最大值 $1$，但我们可以一次操作给两个位置都加 $1$ 吗？可以，折叠使它们重叠，然后滴一次染料，所以 $f=1$。最大值 $1$ ✓

考虑 $[2]$：最大值 $2$，$f=2$（需要两次操作，因为一次只能加 $1$）✓

所以 $f(b) = \max(b)$！因为：

• 每次操作最多给任意位置加 $1$，所以至少需要 $\max(b)$ 次操作
• 可以通过折叠使所有需要达到 $\max(b)$ 的位置重叠，然后滴 $\max(b)$ 次染料

等等，这个推理有问题：如果 $b = [1,2]$，最大值 $2$，但 $f$ 是多少？位置2需要2，位置1需要1。我们可以：第一次操作折叠，使位置1和2重叠，滴一次，得到 $[1,1]$；第二次操作不折叠，只在位置2滴一次，得到 $[1,2]$。所以 $f=2$，等于最大值。

考虑 $b = [2,1]$：同样 $f=2$。

考虑 $b = [2,0,2]$：最大值 $2$，我们可以折叠两端重叠，滴两次染料，得到 $[2,0,2]$。所以 $f=2$。

结论：$f(b) = \max(b)$ 对于所有非负整数数组成立！

验证示例2：$[1,0,0,1,2,1]$ 最大值 $2$，$f=2$ ✓

5. 问题转化

所以原问题变成：

$$\sum_{l=1}^{n} \sum_{r=l}^{n} \max(a_l, a_{l+1}, \dots, a_r) $$

即：求所有子数组的最大值之和。

6. 求解所有子数组的最大值之和

这是一个经典问题。我们可以用单调栈在 $O(n)$ 时间内解决。

对于每个位置 $i$，找到：

• $left[i]$：左边第一个大于 $a[i]$ 的位置（严格大于，避免重复计算）
• $right[i]$：右边第一个大于等于 $a[i]$ 的位置（大于等于，同样避免重复）

那么以 $a[i]$ 为最大值的子数组个数为：

$$cnt[i] = (i - left[i]) \times (right[i] - i)$$

贡献为：

$$ans = \sum_{i=1}^{n} a[i] \times cnt[i]$$

7. 算法步骤

1. 使用单调栈从左到右计算 $left[i]$
2. 使用单调栈从右到左计算 $right[i]$
3. 计算每个位置的贡献并求和
4. 对 $998244353$ 取模

时间复杂度：$O(n)$ 每个测试用例
空间复杂度：$O(n)$

---

C++ 代码实现

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

const int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> left(n), right(n);
    stack<int> st;
    
    // 计算左边第一个大于 a[i] 的位置
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    
    while (!st.empty()) st.pop();
    
    // 计算右边第一个大于等于 a[i] 的位置
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] < a[i]) {
            st.pop();
        }
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long cnt = (long long)(i - left[i]) * (right[i] - i) % MOD;
        ans = (ans + (long long)a[i] % MOD * cnt) % MOD;
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}