CF2043C 题解

题意

给定一个除了 \(-1,1\) 之外，最多存在一个 \(x，x\in[-10^9,10^9]\) 的数的序列，求其子段和的所有可能值，从小到大输出。

分析

很容易就去思考如何从这个特殊的 \(x\) 入手。于是先排除这个特例，考虑全都是 \(1,-1\) 的情形，那么顺序从左到右不断加入 \(a_i\) ，可以发现可以通过维护当前值域的上下界来解决问题。最后我们对于 \(x\) 之前的数统计一遍， \(x\) 之后的数倒序统计一遍，然后通过 \(x\) 把两边合并起来就好了。

赛时就是这么想的，思路也大体正确了。

但是存在的一个问题是，值域中的某些数，可能并不能和当前这个 \(a_i\) 拼接到一起，因为它可能不是以 \(a_{i-1}\) 结尾的。比赛的时候是这么写的，很麻烦，最后也没有调出来。

值域统计

不妨换一个角度思考，一个 \([l,r]\) 的子段和可以表示为 \(sum_r-sum_{l-1}\)，由于 \(x\) 比较特殊，我们还是像上文提到的那样对于 \(x\) 的两边分别统计，最后单独考虑 \(x\)。

这样对于一个固定的 \(i\) 来说，\(sum_i-sum_j\) 的取值一定是在整数意义下连续的。因为任意的 \(sum_i\) 和 \(sum_{i-1}\) 相比，绝对值只会相差 \(1\) ，这就是 \(1,-1\) 的带来的特殊性。（这段比较抽象，建议画一个 \(s_i\) 的散点图来理解）

所以只需要考虑前缀和的前缀 \(max\) 和 \(min\) 就可以了，对于一个 \(s_i\)，\([s_i-pmax,s_i-pmin]\) 之间的所有整数一定都是可以取到的，这样我们就成功计算出了以 \(a_i\) 为结尾的子段值域。

注意，这仅仅是以 \(a_i\) 为结尾的值域情况，我们不断维护它，是为了到最后能和 \(x\) 拼接起来，但是如果直接把它当成答案，肯定会有所遗漏，因为答案子段的结尾并不仅仅只是一个固定的元素，因此，对于所有算出来的值域，我们要取并集。

至于这个取并集过程的实现，观察到相邻两个元素的值域相差不会太大，我们只需要把每次更新值域后 被遗漏的部分提前标记为 true 就可以了。当然，在差分数组上操作，最后前缀和一遍的 trick 也是可以的。

以上是对于 \(x\) 左侧的计算方法，对于 \(x\) 的右侧来说，倒序枚举如法炮制即可。

对 \(x\) 两侧的值域进行合并

记 \(x\) 对应的下标为 \(pos\)。

假设左边以 \(a_{pos-1}\) 为结尾的值域是 \([l,r]\)，右边以 \(a_{pos+1}\) 为结尾的值域是 \([L,R]\)。

很明显的是，最后能够取到的就是 \([x,x]\cup[l+x,r+x]\cup[L+x,R+x]\cup[l+L+x,r+R+x]\)，把这一部分并进答案即可。

我个人的实现方法过于抽象，不过最后还是过了就行。

记得要单独把 \(0\) 也标记为 true。

Code

#include<bits/stdc++.h>
using namespace std;
int T,n;
const int N=2e5+10;
int a[N];
set<int> les,mor;
vector<int> output;
inline void out(set<int> &s){for(int x:s)cout<<x<<' ';}
inline void solve()
{
    cin>>n;
    les.clear(),mor.clear(),output.clear();
    vector<int> vis(2*n+10,0);
    auto upd=[&](int l,int r)
    {
        for(int i=l;i<=r;++i)
        {
            if(i<-n)les.insert(i);
            else if(i>n)mor.insert(i);
            else vis[i+n]=1;
        }
    };
    for(int i=1;i<=n;++i)cin>>a[i];
    int pos=n+1>>1;//随便钦定一个位置即可
    for(int i=1;i<=n;++i)if(a[i]!=1&&a[i]!=-1){pos=i;break;}
    int l=0,r=0,s=0;
    int mx=0,mn=0;
    for(int i=1,nowl,nowr;i<pos;++i)
    {
        s+=a[i];
        nowl=s-mx,nowr=s-mn;
        for(int j=l;j<nowl;++j)vis[j+n]=1;
        for(int j=r;j>nowr;--j)vis[j+n]=1;
        mx=max(mx,s),mn=min(mn,s);
        l=nowl,r=nowr;
    }
    int L=0,R=0;
    s=0,mx=0,mn=0;
    for(int i=n,nowl,nowr;i>pos;--i)
    {
        s+=a[i];
        nowl=s-mx,nowr=s-mn;
        for(int j=L;j<nowl;++j)vis[j+n]=1;
        for(int j=R;j>nowr;--j)vis[j+n]=1;
        mx=max(mx,s),mn=min(mn,s);
        L=nowl,R=nowr;
    }
    int x=a[pos];
    upd(l,r);
    upd(L,R);
    upd(x,x);
    upd(l+x,r+x);
    upd(L+x,R+x);
    upd(l+L+x,r+R+x);
    vis[n]=1;
    for(int i=-n;i<=n;++i)if(vis[i+n])output.push_back(i);
    cout<<les.size()+output.size()+mor.size()<<'\n';
    out(les);
    for(int val:output)cout<<val<<' ';
    out(mor);
    cout<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}