CF2053I Affectionate Arrays 题解

IvanZhang2009 · 2024-12-29 20:28:16 · 题解

注意到 \max(|a_i|)\le \sum a_i 的限制。经过合理猜测可以发现 b 最大子段和最小就是 \sum a_i，取整个序列即可得到。考虑一个深刻的充要条件：设 s=\sum a_i，则 b_i 的任意前缀和值域都在 [0,s]。

• 考虑一个前缀 a_{1\dots k} 的和 <0，则取后面的部分的和超过了 s。
• 考虑一个前缀 a_{1\dots k} 的和 >s，则取这段前缀的和超过了 s。
• 满足值域限制的条件下，一个子段和可以描述成两个前缀和相减的形式，显然这个差也在 [-s,s] 中。

所以这是充要的。我们考虑直接对前缀和设计 dp：f_{i,j} 表示长度为 i 的前缀加若干个数得到和为 j 的前缀，最少需要添加多少个数。考虑转移，需要观察题目的特殊性质：考虑每两个数之间以及头尾的总共 n+1 个空挡，只会在每个空挡里填恰好一个数。我们不妨把开头的空用来初始化状态，令 f_{0,i}=[i>0]。之后转移的时候首先要求 a_{i}+j'\in[0,s]，然后才能找到 k 令 f_{i-1,j}\rightarrow f_{i,j+a_i+k}。时间复杂度 O(ns^2)，不可接受。也可以注意到这个转移是一个区间和、区间 min 的形式，可以做到 O(ns)。

考虑把 f 数组打个表看看，可以发现对于 i 固定时，同一个 f_{i,j} 在 j\in[0,s] 时只有不超过两个不同的值，且更小的那个形成一段区间。考虑归纳证明，初始时只有 0,1 的不同值，且值为 0 的构成区间 [0,0]。转移时先 ban 掉一段区间（要求 j'+a_i\in[0,s]），此时值更小的仍然是区间（但是可能使全局相等，需要特殊处理），然后转移后值仍然等于更小值的点相当于把原区间沿着 a_i 方向平移（不加更多数，保留 f 值），于是仍然是区间，可以发现剩下的部分答案都是更小值加一。我们直接 O(1) 维护这些区间可以维护出 f 数组最后的值，求出 f_s 即是最小长度 -n。于是在 O(n) 时间内解决了最小长度。

下面是代码。很短吧！

#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
int n,s;
int a[3000005];
void Main() {
    cin>>n;s=0;
    REP(i,0,n)cin>>a[i],s+=a[i];
    int cur=0,l=0,r=0;
    REP(i,0,n){
        int L=max(0ll,-a[i]),R=min(s,s-a[i]);
        if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
        else l=L,r=R,++cur;
        l+=a[i];r+=a[i];
        l=max(l,0ll);r=min(r,s);
        if(l>r)l=0,r=s,++cur;
    }
    over(cur+n+(r!=s))
}
void TC() {
    int tc=1;
    cin>>tc;
    while(tc--){
        Main();
        cout.flush();
    }
}
signed main() {
    return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}

当然这篇题解到这里还没有结束。原题是一个计数，但是因为各种原因被删掉了。这里也一起分享出来。

update：I2 改成符合 std 的题意之后回归了！所以我们改变一下说法。考虑现在的新题意怎么做！

原 std 的做法针对“数合法序列 b”是假的，原因是在一个数两边的空隙插入一个值相同的数应当算同一种方案，而按插空隙的做法来做是算多种，即会算重。

新版题意改成了“a 在所有合法序列 b 中的出现次数和”。考虑这个如何转化。注意到算重的部分在同一个连续段只会出现一次。设我们在长度为 x 的值为 y 的段中插入一个 y （注意如果中间不再插别的数则只可能插入一个 y），出现次数的贡献是 x+1，而恰好我们的做法算重的次数也是 x+1。所以我们大胆算重去计数即可！

扩展 I1 的做法，考虑方案数的转移，设 g_{i,j} 为同定义下的方案数。区间平移的部分，g 的转移仍然是区间平移，并在下文称之为【特殊区间】。不妨考虑 a_i>0 的情况，一开始 ban 掉的是 [0,a_i-1] 的部分，而后面补进来这部分的时候，这些的 g 值都相等，等于原本 g 中 f 更大的所有值的 g 和。而对于既不是这一块又不是特殊区间的部分，将会在原值的基础上加上上面对应的 g 和。

总结一下就是前后缀删点，前后缀加值为 0 的连续段，对非特殊区间做区间加。我们不进行区间平移，而是维护 tag 表示区间的平移量即可把问题静态化，做到 O(s\log s)，但是仍然不可接受。

我们观察转移的过程，发现少有单点操作，都是对着整段的区间做操作，例如前后缀塞一个连续段，前后缀删连续段，这启发我们不仅是 f，g 的值也可以形成若干段连续段。经过打表验证，可以发现 g 的值确实形成 O(n) 个连续段。由于要支持前后缀操作，我们直接开一个 deque 维护所有连续段的所有信息，包括左右端点和每个点的 g 值。为了维护信息，我们需要维护：tpos 表示当前区间整体平移的偏移量；l,r 表示特殊区间为 [l+tpos,r+tpos]；tv_1,tv_2 表示特殊和非特殊区间的全局加的标记（需要支持这些全局加）；s_1,s_2 表示特殊和非特殊区间的权值和（需要支持整体加，而加的值就是非特殊区间的答案和）。注意到这些都可以在维护 push，pop 操作的同时维护出来。一个大细节是 pop 区间后可能会出现全局 f 相等的情况，即 [l,r] 变成整区间，此时会用到维护的非特殊区间的全局加标记和全局和，所以才两个都要维护。每个连续段被插入一次删除一次，push 次数为 n，于是时间复杂度均摊 O(n)。可以讨论 a_i 的正负性转移。

给出我的实现：

#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
struct interval{
    int l,r,g;
    int calc(int tg=0){return ((r-l+1)*(tg+g))%MOD;}
};
int n,s;
int a[3000005];
#define inside(x) (x.l>=l&&x.r<=r)
void Main() {
    cin>>n;s=0;
    REP(i,0,n)cin>>a[i],s+=a[i];
    if(s<*max_element(a,a+n))assert(0)
    if(s<-*min_element(a,a+n))assert(0);
    if(!s)over(1)
    deque<interval>dq;
    dq.pb({0,0,1});dq.pb({1,s,1});
    int tpos=0,tval=0,l=0,r=0,sum1=1,sum2=s,tv2=0;
    REP(i,0,n){
        if(a[i]>=0){
            while(dq.size()&&dq.back().l+tpos>s-a[i]){
                if(inside(dq.back()))sum1-=dq.back().calc(tv2);
                else sum2-=dq.back().calc(tval);
                dq.pop_back();
            }
            if(dq.back().r+tpos>s-a[i]){
                if(inside(dq.back()))sum1-=(dq.back().g+tv2)*(dq.back().r+tpos-(s-a[i]))%MOD;
                else sum2-=(dq.back().r+tpos-(s-a[i]))*(tval+dq.back().g)%MOD;
                dq.back().r=s-a[i]-tpos;
            }
            sum1=(MOD+sum1%MOD)%MOD;
            sum2=(MOD+sum2%MOD)%MOD;
            r=min(r,s-a[i]-tpos);
            if(l>r){
                l=dq.front().l;r=dq.back().r;
                sum1=sum2;sum2=0;tv2=tval;tval=0;
            }
            if(a[i])dq.push_front({dq[0].l-a[i],dq[0].l-1,(MOD-tval)%MOD});
            tpos+=a[i];(tval+=sum1)%=MOD;(sum2+=sum1*(s+1-(r-l+1)))%=MOD;
        }else{
            a[i]*=-1;
            while(dq.size()&&dq.front().r+tpos<a[i]){
                if(inside(dq.front()))sum1-=dq.front().calc(tv2);
                else sum2-=dq.front().calc(tval);
                dq.pop_front();
            }
            if(dq.front().l+tpos<a[i]){
                if(inside(dq.front()))sum1-=(dq.front().g+tv2)*(a[i]-dq.front().l-tpos)%MOD;
                else sum2-=(a[i]-dq.front().l-tpos)*(dq.front().g+tval)%MOD;
                dq.front().l=a[i]-tpos;
            }
            sum1=(MOD+sum1%MOD)%MOD;
            sum2=(MOD+sum2%MOD)%MOD;
            l=max(l,a[i]-tpos);
            if(l>r){
                l=dq.front().l;r=dq.back().r;
                sum1=sum2;sum2=0;tv2=tval;tval=0;
            }
            dq.push_back({dq.back().r+1,dq.back().r+a[i],(MOD-tval)%MOD});
            tpos-=a[i];(tval+=sum1)%=MOD;(sum2+=sum1*(s+1-(r-l+1)))%=MOD;
        }
    }
    cout<<(dq.back().g+(inside(dq.back())?tv2:tval))%MOD<<endl;
}
void TC() {
    int tc=1;
    cin>>tc;
    while(tc--){
        Main();
        cout.flush();
    }
}
signed main() {
    return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}

其实这篇题解到这里还是没有结束。作为名义上的 writer，出锅之后我还得修，于是考虑原版题意的计数。能否改进 std 的做法呢？尝试对于同一个数的连续段 dp，发现似乎很困难。irris 和我都放弃了。

我们从问题的本质上入手。不妨直接对着序列 b 做 dp，并把子序列的限制放到状态中。设 f(i,j,k) 表示填了 b 序列的前 i 项，匹配序列 a 最多能匹配 j 项，当前前缀和为 k 的方案数。我们不妨先套用 I1 的 dp 求出这个最小长度 m，这样状态数是 O(mns)=O(n^2s)。转移时可以枚举下一个数填什么，是 O(s) 的。提供一个代码主要部分。

int n;
int a[3000005];
int dp[105][105][1005];
int s;
int qlen(){
    int cur=0,l=0,r=0;
    REP(i,0,n){
        int L=max(0ll,-a[i]),R=min(s,s-a[i]);
        if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
        else l=L,r=R,++cur;
        l+=a[i];r+=a[i];
        l=max(l,0ll);r=min(r,s);
        if(l>r)l=0,r=s,++cur;
    }
    return cur+(r<s)+n;
}
void Main() {
    cin>>n;
    REP(i,0,n)cin>>a[i];
    s=accumulate(a,a+n,0ll);
    int m=qlen();
    REP(i,0,m+1){
        REP(j,0,n+1){
            REP(l,0,s+1)dp[i][j][l]=0;
        }
    }
    dp[0][0][0]=1;
    REP(i,0,m){
        REP(j,0,n+1){
            REP(l,0,s+1)if(dp[i][j][l]){
                REP(p,-l,s-l+1){
                    int j2=j+(j<n&&a[j]==p);
                    (dp[i+1][j2][l+p]+=dp[i][j][l])%=MOD;
                }
            }
        }
    }
    cout<<dp[m][n][s]<<endl;
}

可以发现这个 O(s) 转移容易做到 O(1)。具体地，我们转移 f(i,j,k)，先接收所有 f(i-1,j,l) 的值（毕竟都可以加一个数得到），然后再考虑其它特殊的。如果加入一个数之后可以匹配，就减掉 f(i-1,j,l-a_j)。如果是加入一个数之后匹配了，就加上 f(i-1,j-1,l-a_{j-1})。时间复杂度 O(n^2s)。

int n;
int a[3000005];
int dp[105][105][1005];
int s;
int qlen();//和上面相同，省略
void Main() {
    cin>>n;
    REP(i,0,n)cin>>a[i];
    s=accumulate(a,a+n,0ll);
    int m=qlen();
    REP(i,0,m+1){
        REP(j,0,n+1){
            REP(l,0,s+1)dp[i][j][l]=0;
        }
    }
    dp[0][0][0]=1;
    REP(i,0,m){
        REP(j,0,n+1){
            int sum=0;
            REP(l,0,s+1){
                sum+=dp[i][j][l];
            }
            REP(l,0,s+1){
                dp[i+1][j][l]=sum;
                if(j<n&&l>=a[j]&&l-a[j]<=s)dp[i+1][j][l]-=dp[i][j][l-a[j]];
                if(j>0&&l>=a[j-1]&&l-a[j-1]<=s)dp[i+1][j][l]+=dp[i][j-1][l-a[j-1]];
                (dp[i+1][j][l]+=MOD)%=MOD;
            }
        }
    }
    cout<<dp[m][n][s]<<endl;
}

考虑原做法的连续段想法。我们把 s 那一维用连续段刻画，即将其划分成 \rm{poly}(n) 个方案数相同的连续段，然后利用归并的方式合并即可。细节相当于把 f(i,j-1) 和 f(i,j) 分别平移对应距离后相减，然后做全局加。时间复杂度 O(n^{k+2})，其中长度为 s 的数组可以划分成 O(n^k) 段。k 具体是多少我也不太懂，反正至少是 2。

int n;
int a[3000005];
int s;
struct structures{
    int l,r,val;
};
#define vs vector<structures>
vs f[30005],g[30005];
int qlen();//和上面相同，省略
vs mover(vs a,int x){
    if(!x)return a;
    vs b;
    if(x>0)b.pb({0,x-1,0});
    for(auto [l,r,val]:a){
        int L=l+x,R=r+x;
        L=max(L,0ll);R=min(R,s);
        if(L<=R)b.pb({L,R,val});
    }
    if(x<0)b.pb({s+x+1,s,0});
    return b;
}
vs operator -(vs a,vs b){
    vector<int>t;
    int x=0,y=0,n=a.size(),m=b.size();
    while(x<n&&y<m){
        if(a[x].l==b[y].l)t.pb(a[x].l),++x,++y;
        else if(a[x].l<b[y].l)t.pb(a[x++].l);
        else t.pb(b[y++].l);
    }
    while(x<n)t.pb(a[x++].l);
    while(y<m)t.pb(b[y++].l);
    n=t.size();t.pb(s+1);
    vs c(n,{0,0,0});
    REP(i,0,n)c[i].l=t[i],c[i].r=t[i+1]-1;
    x=0;
    for(auto [l,r,val]:a){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=val,++x;
    }
    x=0;
    for(auto [l,r,val]:b){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=MOD-val,++x;
    }
    REP(i,0,n)c[i].val%=MOD;
    a.clear();
    int lstval=-1;
    for(auto [l,r,val]:c){
        if(val==lstval)a[a.size()-1].r=r;
        else a.pb({l,r,lstval=val});
    }
    return a;
}
void Main() {
    cin>>n;
    REP(i,0,n)cin>>a[i];
    s=accumulate(a,a+n,0ll);
    int m=qlen();
    REP(i,0,n+1){
        f[i].clear();
        g[i].clear();
        if(i)g[i]=vs(1,{0,s,0});
        else{
            g[i].pb({0,0,1});g[i].pb({1,s,0});
        }
    }
    REP(i,0,m){
        for(int j=n;j>=0;--j){
            int sum=0;
            for(auto [l,r,val]:g[j])(sum+=(r-l+1)%MOD*val)%=MOD;
            vs s1=j<n? mover(g[j],a[j]):vs(1,{0,s,0}),s2=j? mover(g[j-1],a[j-1]):vs(1,{0,s,0});
            g[j]=s2-s1;
            for(auto &l:g[j])(l.val+=sum)%=MOD;
        }
    }
    int x=g[n].size()-1;
    cout<<g[n][x].val<<endl;
}

然后再加入最优性。注意到对于一个 i，使 f 有值的 j 一定是一个前缀 j\le R_i。这可以理解为，给定你 i 个可以加入的数，最多能匹配 a 中的几位。这个翻转之后可以变成：对于 a 的每个前缀，它最少添加几位。

同理，j 也应该有下界 j\ge L_i。这可以理解为，对于这个后缀，你只有若干个数可以加，最长能匹配的后缀，也就是最短需要能匹配的前缀。可以通过倒着做一样的 dp 解决。根据“两个数之间只能插一个”的理论，可以发现 R_i-L_i+1\le 2，也就是对于一个 i 只有最多 2 个 j 是有用的。只转移这些，可以证明 s 那一维只有 O(n^2) 且跑不满个连续段，于是时间复杂度 O(n^3)。

int n;
int a[3000005];
int s;
int mnm[3000005],mxm[3000005];
struct structures{
    int l,r,val;
};
#define vs vector<structures>
vs f[3000005],g[3000005];
int m;
int qlen(){
    int cur=0,l=0,r=0;
    mnm[0]=0;
    REP(i,0,n){
        int L=max(0ll,-a[i]),R=min(s,s-a[i]);
        if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
        else l=L,r=R,++cur;
        l+=a[i];r+=a[i];
        l=max(l,0ll);r=min(r,s);
        if(l>r)l=0,r=s,++cur;
        mnm[i+1]=cur+i+1;
    }
    return cur+(r<s)+n;
}
void getdp_back(){
    int cur=0,l=0,r=0;
    mxm[n]=m;
    for(int i=n-1;i>=0;--i){
        int L=max(0ll,-a[i]),R=min(s,s-a[i]);
        if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
        else l=L,r=R,++cur;
        l+=a[i];r+=a[i];
        l=max(l,0ll);r=min(r,s);
        if(l>r)l=0,r=s,++cur;
        mxm[i]=m-n-cur+i;
    }
}
vs mover(vs a,int x){
    if(!x)return a;
    vs b;
    if(x>0)b.pb({0,x-1,0});
    for(auto [l,r,val]:a){
        int L=l+x,R=r+x;
        L=max(L,0ll);R=min(R,s);
        if(L<=R)b.pb({L,R,val});
    }
    if(x<0)b.pb({s+x+1,s,0});
    return b;
}
vs operator -(vs a,vs b){
    vector<int>t;
    int x=0,y=0,n=a.size(),m=b.size();
    while(x<n&&y<m){
        if(a[x].l==b[y].l)t.pb(a[x].l),++x,++y;
        else if(a[x].l<b[y].l)t.pb(a[x++].l);
        else t.pb(b[y++].l);
    }
    while(x<n)t.pb(a[x++].l);
    while(y<m)t.pb(b[y++].l);
    n=t.size();t.pb(s+1);
    vs c(n,{0,0,0});
    REP(i,0,n)c[i].l=t[i],c[i].r=t[i+1]-1;
    x=0;
    for(auto [l,r,val]:a){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=val,++x;
    }
    x=0;
    for(auto [l,r,val]:b){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=MOD-val,++x;
    }
    REP(i,0,n)c[i].val%=MOD;
    a.clear();
    int lstval=-1;
    for(auto [l,r,val]:c){
        if(val==lstval)a[a.size()-1].r=r;
        else a.pb({l,r,lstval=val});
    }
    return a;
}
void Main() {
    cin>>n;
    REP(i,0,n)cin>>a[i];
    s=accumulate(a,a+n,0ll);
    m=qlen();getdp_back();
    REP(i,0,n+1){
        g[i].clear();
        if(i)g[i]=vs(1,{0,s,0});
        else{
            g[i].pb({0,0,1});g[i].pb({1,s,0});
        }
    }
    int xl=0,xr=0;
    REP(i,0,m){
        int lxl=xl,lxr=xr;
        while(xl<=n&&mxm[xl]<i+1)++xl;
        while(xr+1<=n&&mnm[xr+1]<=i+1)++xr;
        for(int j=xr;j>=xl;--j){
            ++cnt;
            int sum=0;
            for(auto [l,r,val]:g[j])(sum+=(r-l+1)%MOD*val)%=MOD;
            vs s1=j<n? mover(g[j],a[j]):vs(1,{0,s,0}),s2=j? mover(g[j-1],a[j-1]):vs(1,{0,s,0});
            g[j]=s2-s1;
            for(auto &l:g[j])(l.val+=sum)%=MOD;
        }
        REP(i,lxl,xl)g[i]=vs(1,{0,s,0});
    }
    int x=g[n].size()-1;
    cout<<g[n][x].val<<endl;
}

很抱歉实力有限，当天的补救中我只能做到这了。当时是赶工到凌晨五点才写完的这个东西，第二天发现没人会更优的，做不到 3\times 10^6 的范围，于是只能删掉这个题了。

如果大家有更好的想法欢迎沟通。