题解：CF2077E Another Folding Strip

· · 题解

挺有意思的一道题，部分内容参考官方题解，本题解将对所有的结论给出严谨证明。

首先转化掉折叠操作，显然对于两个奇偶性相同的下标，无论怎么折叠都无法使它们重合。进一步地，不难发现一次操作其实等价于选出一个相邻下标奇偶性不同的子序列都 +1，充分性考虑假如选择的子序列下标为 i_1,i_2,\ldots,i_m 且 i_j 和 i_{j+1} 奇偶性不同，令中间的 m-1 个折痕的方向向左向右交替，一定能得到一个合法的折叠方式。

先考虑怎么计算整个 a 序列的答案，不妨把问题倒过来看，变成每次选择 a 的一个合法子序列依次 -1，然后要把 a 变成全 0。考虑一个比较套路的操作，将 a 黑白染色然后取反，也就是令 b_i=(-1)^ia_i。

注意到一个性质是，对于任意一个子段 [l,r]，对 a 序列进行任意一次操作之后 \sum_{i=l}^r b_i 的值只有不变，+1 和 -1 三种情况，这取决于 [l,r] 中有几个位置被选进操作的子序列，也就是说 |\sum_{i=l}^rb_i| 的变化量不超过 1，所以可以分析出来答案的一个下界是 \max_{1\le l\le r\le n}|\sum_{i=l}^r b_i|，也就是序列 b 绝对值最大的子段和。

令一次操作选择的子序列的下标集合为 S，我们用这么一个贪心的策略来确定每次的 S：

我们声称，重复此过程确定每次操作选择的子序列，即可使答案取到下界，下面给出证明。

令 T 为一次操作前所有使得 |\sum_{i=l}^rb_i| 取到最大值且 b_l,b_r\not= 0 的 (l,r) 集合，只需要说明 \forall (l,r)\in S 在操作后 |\sum_{i=l}^r b_i| 一定恰好减少 1 即可。

首先要观察到，每对 (l,r) 的奇偶性是相同的，因为如果不同则 b_l 和 b_r 是异号的，去掉其中一个一定可以使绝对值变大。

一个重要的结论是，\forall (l,r)\in T，一定有 l\in S。考虑反证法，假如 l\not\in S，说明 S 中存在一个 k<l，满足 k 与 l 奇偶性相同，且 k 与 l 中间和 l 奇偶性不同的位置都是 0，此时直接把 l 移动到 k 显然绝对值会更大，矛盾。

可以发现的是，此时 \forall (l,r)\in T，[l,r] 中被选到 S 中的位置一定有奇数个。同样考虑反证法，假如是偶数个，那么 S 中最后一个 \le r 的位置 d 一定与 l,r 的奇偶性不同，说明下一个与 l,r 奇偶性相同且非 0 的位置 >r，与 T 定义中的 b_r\not=0 矛盾。

如果 l 为奇数，那么 b_{[l,r]} 中被选择的位置变化量形如 +1,-1,+1,\ldots,-1,+1，总共为 1，显然 l 为奇数时原来的 \sum_{i=l}^rb_i<0，所以此时绝对值会减少 1。

如果 l 为偶数，那么 b_{[l,r]} 中被选择的位置变化量形如 -1,+1,-1,\ldots,+1,-1，总共为 -1，显然 l 为偶数时原来的 \sum_{i=l}^r b_i>0，所以此时绝对值会减少 1。

综上，我们说明了这种贪心策略能使答案取到下界。

官方题解在证明过程中写到 \forall (l,r)\in T 还有 r\in S 成立，笔者认为这是错误的，考虑 b=\{-3,0,-3\}，则显然 T=\{(1,3)\} 且 S=\{1\}。如果确为官方题解笔误或者是我的理解错误，请您在评论区指出/bx/bx/bx。

因此对于整个序列 a，我们只需要求对应的 \max_{1\le l\le r\le n}|\sum_{i=l}^rb_i| 即为答案，显然这个值等于 b 序列前缀和数组的极差。回到原题，再对 b 数组做一遍前缀和，问题就变成了类似于求所有子区间极差和的形式，这是一个经典问题，分治，扫描线，单调栈，随便选择一个你喜欢的做法求出即可。

这里使用了单调栈实现，时间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
int n, a[N], b[N];
int top, ans, st[N], L[N], R[N];
inline void add(int &x, int y){x += y; if(x >= mod) x -= mod;}
inline void sub(int &x, int y){x += mod - y; if(x >= mod) x -= mod;}
void Solve(){
    cin >> n;
    For(i, 1, n) cin >> a[i];
    For(i, 1, n){
        if(i & 1) b[i] = b[i - 1] + a[i];
        else b[i] = b[i - 1] - a[i];
    }
    top = ans = 0;
    For(i, 1, n) R[i] = n;
    For(i, 1, n){
        while(top && b[st[top]] < b[i]) R[st[top]] = i - 1, top--;
        L[i] = !top ? 0 : st[top] + 1; st[++top] = i;
    }
    For(i, 1, n) (ans += (R[i] - i + 1) * (i - L[i] + 1) % mod * (b[i] % mod) % mod) %= mod;
    top = 0;
    For(i, 1, n) R[i] = n;
    For(i, 0, n){
        while(top && b[st[top]] >= b[i]) R[st[top]] = i - 1, top--;
        L[i] = !top ? 0 : st[top] + 1; st[++top] = i;
    }
    For(i, 1, n) (ans -= (R[i] - i + 1) * (i - L[i] + 1) % mod * (b[i] % mod) % mod) %= mod;
    ans = (ans % mod + mod) % mod;
    cout << ans << '\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T = 1; cin >> T;
    while(T--) Solve();
    return 0;
}