CF1913D Array Collapse

spider_oyster · 2023-12-20 08:59:32 · 题解

设 f_i 表示以 a_i 结尾的子序列个数。

假设我们要从 f_j 转移到 f_i，考虑需要满足什么条件。

如果 \min\{a_i,a_j\}=\min\limits_{i\leq k \leq j}\{a_k\}，那么可以接上。

考虑分两种情况，a_i 为区间最小值，用单调栈维护从 i 往左边第一个位置 l_i，满足 a_{l_i}<a_i，那么区间左端点为 [l_i+1,i] 的区间都满足这个条件。

对于 a_j 为区间最小值，满足条件的 j 就是当前单调栈里的剩余所有元素。设当前单调栈元素 f 之和为 sum，那么有：

注意，当当前单调栈为空的时候， a_i 可以作为一个子序列的开头。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=3e5+5,p=998244353;
int n,m,top,a[N],f[N],s[N],stk[N];

inline int rd()
{
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x;
}

void solve()
{
    n=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    int sum=0;top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[stk[top]]>a[i]) sum=(sum-f[stk[top]]+p)%p,top--;
        f[i]=(sum+s[i-1]-s[stk[top]]+(top==0)+p)%p;
        s[i]=(s[i-1]+f[i])%p;
        stk[++top]=i,sum=(sum+f[i])%p;
    }
    cout<<sum<<'\n';
}

signed main()
{
    int t=rd();
    while(t--) solve();
}