题解：CF2043C Sums on Segments

· · 题解

题意

给你一个长度为 n 的数组 a，满足 a 中有且仅有一个不为 1 也不为 -1 的数（以下简称特殊的值），剩余的数都是 1 或 -1。求所有可能的子区间的和的值（下文简称答案）。从小到大一次输出每一个值，每个值只输出一遍。

题解

首先，我们发现，如果把那个特殊的值考虑进来不那么好搞，而又“有且仅有一个不为 1 也不为 -1 的数”，于是我们考虑把 a 数组从那个特殊的值那里分成两段，他左边的成一段，他右边的另成一段，他自己提出来。然后我们就从考虑一个大问题分成了三个子问题：左边区间的所有可能的子区间的和的值，右边区间所有可能的子区间的和的值，包含特殊的值的所有可能的子区间的和的值。

左边区间 & 右边区间

这里有个不怎么显然的结论：在一个值域为 \{1,-1\} 的数组里，设他的最大子段和是 a，最小子段和是 b。那么，有且仅有属于 [b,a] \cap \mathbb{Z} 的数是答案，且这个集合里的每一个数都是答案。有了这个结论，左边区间的答案和右边区间的答案都好求了，但是，结论固然得证，所以我们就来证这个结论。

我们找到能造成最大子段和 a 的区间，然后，将它分成 a 个和为 1 的子区间，能够证明一定有分法。然后，如果我们想得到和为 a - 1 的子区间，我们只需要从左边或者右边去掉一个和为 1 的子区间就能得到。对于 a - 2,a - 3, \cdots 1 都可以用这种方法得出。于是我们就证得属于 [1,a] \cap \mathbb{Z} 的数一定是答案。如法炮制，我们也能证出属于 [b,-1] \cap \mathbb{Z} 也一定是答案。最后并上一个 {0}，就得到了 [b,a] \cap \mathbb{Z}。这样我们就成功的求出了左边区间和右边区间的答案。

包含特殊值的区间

也是如法炮制，不过因为要包含特殊值，所以就不能简单的求最大（小）字段和，要求最大（小）前（后）缀和。对于左边区间就是后缀，对于右边，就是前缀。然后我们设左边的最大后缀和是 max_{1}，最小后缀和是 min_{1}。右边的最大前缀和是 max_{2}，最小前缀和是 min_{2}，那么包含特殊值的区间的答案区间就是 [min_{1} + min_{2} + val,max_{1} + max_{2} + val] \cap \mathbb{Z}。这里 val 指特殊值。

code

#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
int n,val,pos,sum;
int max1,min1,max2,min2;
int a[maxn],dp1[maxn],dp2[maxn];
void solve()
{
    cin >> n;
    pos = val = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] != 1 && a[i] != -1)
        {
            val = a[i];
            pos = i;
        }
    }
    max1 = min1 = 0;
    fill(dp1 + 1,dp1 + n + 1,0);
    fill(dp2 + 1,dp2 + n + 1,0);
    for (int i = 1; i <= pos - 1; i++)   
    {
        dp1[i] = max(dp1[i - 1] + a[i],0ll);
        max1 = max(max1,dp1[i]);//求左边区间的最大子段和
        dp2[i] = min(dp2[i - 1] + a[i],0ll);
        min1 = min(min1,dp2[i]);//求左边区间的最小子段和
    }
    max2 = min2 = 0;
    fill(dp1 + 1,dp1 + n + 1,0);
    fill(dp2 + 1,dp2 + n + 1,0);
    for (int i = pos + 1; i <= n; i++)
    {
        dp1[i] = max(dp1[i - 1] + a[i],0ll);
        max2 = max(max2,dp1[i]);//求右边区间的最大
        dp2[i] = min(dp2[i - 1] + a[i],0ll);
        min2 = min(min2,dp2[i]);//求右边区间的最小
    }
    set<int>ans;
    for (int i = min(min1,min2); i <= max(max1,max2); i++)
        ans.insert(i);//先把不包含val的值加入
    max1 = min1 = sum = 0;
    for (int i = pos - 1; i >= 1; i--)
    {
        sum += a[i];
        max1 = max(max1,sum);//求左边区间的最大后缀和
        min1 = min(min1,sum);//求左边区间的最小后缀和
    }
    max2 = min2 = sum = 0;
    for (int i = pos + 1; i <= n; i++)
    {
        sum += a[i];
        max2 = max(max2,sum);//如法炮制
        min2 = min(min2,sum);
    }
    for (int i = (min1 + min2); i <= (max1 + max2); i++)
        ans.insert(val + i);//记录答案
    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i << " ";
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

upd:更新几处笔误