题解：CF1585F Non-equal Neighbours

· · 题解

很牛的题，感觉我的做法特魔怔，故写题解记之。

首先我们有一个朴素的二维 DP，我们设 f[i][j] 表示 b_i=j 的方案数，s[i][j]=\sum\limits_{k=1}^{j}f[i][k],g[i]=s[i][a_i]。很显然有转移 f[i][j]=g[i-1]-f[i-1][j]，因为第 i-1 位可以选除了 j 以外的所有数。最终答案即为 g[n]。

特别地，若 a_i<j，则 f[i][j]=0。以及有边界条件 f[1][j]=1(j\in [1,a_1])。

这样我们得到了一个 O(nV) 的做法，显然无法通过，考虑优化。

由于 f[i][j]=g[i-1]-f[i-1][j]，将 j=1,2,...,k(k\le a_i) 代入上式并求和，得到 s[i][k]=k\times g[i-1]-s[i-1][k]。当 k=a_i 时，则有 g[i]=a_i\times g[i-1]-s[i-1][a_i]。

若 a_i\ge a_{i-1}，显然有 s[i-1][a_i]=s[i-1][a_{i-1}]，因为 f[i-1][j]=0(j\in(a_{i-1},a_i])。上式变为 g[i]=(a_i-1)\times g[i-1]。

若 a_i < a_{i-1}，我们考虑求出 s[i-1][a_i]。s[i-1][a_i]=a_i\times g[i-2]-s[i-2][a_i]。注意到这个形式与上式几乎一样，我们只需递归地找到第一个 j< i 满足 a_{i-j}\le a_i 即可。有 g[i]=a_i\times(g[i-1]-g[i-2]+...\pm g[i-j])\mp g[i-j]。若不存在这样的 j，即当 a_i 是 a 的严格前缀最小值时，此时即求 s[1][a_i]，即为 a_i。不是 \min(a_1,a_i) 是因为此时 a_i 必然小于 a_1。

我们只需使用单调栈对于每一个 i 求出对应的 j，再使用前缀和与奇偶性分类维护形如 g[i-1]-g[i-2]+...\pm g[i-j] 的结果即可。时间复杂度 O(n)，可通过本题。

#include<bits/stdc++.h>
#define int long long
#define gc getchar
//char buf[1<<20],*p1,*p2;
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define R read()
using namespace std;
int read()
{
    int x=0,f=1;
    char c=gc();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=gc();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=gc();
    return x*f;
}
void write(int x,char xx)
{
    static int st[35],top=0;
    if(x<0){x=-x;putchar('-');}
    do
    {
        st[top++]=x%10,x/=10;
    }while(x);
    while(top) putchar(st[--top]+48);
    putchar(xx);
}
#define N 200010
#define mod 998244353
int n,a[N],f[N],l[N],s[N];
vector<int>v;
signed main()
{
    n=R;
    for(int i=1;i<=n;i++) a[i]=R;
    for(int i=n;i>=1;i--)
    {
        while(v.size()&&a[v.back()]>=a[i]) l[v.back()]=i,v.pop_back();
        v.push_back(i);
    }
    f[1]=s[1]=a[1]%mod;
    for(int i=2;i<=n;i++) 
    {
        f[i]=s[i-1];
        if(l[i]) (f[i]+=mod-s[l[i]-1])%=mod;
        if(i&1) f[i]=mod-f[i];
        ((f[i]%=mod)+=mod)%=mod;
        f[i]=f[i]*a[i]%mod,(f[i]+=(((i&1)^(l[i]&1))?-1:1)*(l[i]?f[l[i]]:-a[i])+mod)%=mod,s[i]=(s[i-1]+(i&1?f[i]:mod-f[i]))%mod;
    }
    write(f[n],'\n');
    return 0;
}