codeforces D. Array Collapse

DP一生之敌
learn from AC-Panda and codeforces’s Tutorial

思路

• $dp[i]$ 表示以 $a[i]$ 结尾的方案数， $sum[i]$ 表示 $\sum _{j=1}^{i}d{p}_j$ 。
• 对于 $dp[i]$ 当 $DP$ 到 $a[i]$ 后面的数我们思考 $dp[i]$ 是否存在。
• • $a[j]>a[i]$ ，显然可以包含 $contiguoussubsegment[j,n]$ 保证 $dp[i]$ 存在。
• • $a[j]<a[i]$ ，根据题意显然无法做到保留 $a[i]$ 且不保留 $a[j]$ ，此时 $dp[i]$ 不存在。
• • 无法保留但可以替换，就是说对于 $dp[i]$ 我们可以根据题意将其末尾的 $a[i]$ 替换为 $a[j]$ 。
• • $i<k<j$ ，$a[i]$ 是从右往左第一个比 $a[j]$ 小的数，那么所有的 $dp[k]$ 的末尾都可以被 $a[j]$ 替换。
• • $a[j]$ 当然还可以拼接在所有合理方案的后面。
• 用单调栈维护从右往左第一个小的数。
• 单调栈时也要维护 $ans$ ，就是减去不存在的。

Think Twice, Code Once

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define endl '\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int, int> pii;
int read(void) {
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x) {
    if (x < 0) x = -x, put(45);
    if (x > 9) write(x / 10);
    put((x % 10) ^ 48);
}
#define writeln(a) write(a), put(10)
#define writesp(a) write(a), put(32)
#define writessp(a) put(32), write(a)
const int N = 2e5 + 10, M = 1e5 + 10, SN = 1e3 + 10, mod = 998244353;
signed main() {
    int T = 1;
    T = read();
    while (T--) {
        int n = read();
        vector<int> a(n + 1), dp(n + 1), sum(n + 1);
        for (int i = 1; i <= n; ++i) a[i] = read();
        stack<int> sta;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int cnt = 0;
            while (!sta.empty() && a[i] < a[sta.top()]) ans -= dp[sta.top()], sta.pop();
            if (sta.empty()) dp[i] = (sum[i - 1] + 1) % mod;
            else dp[i] = (sum[i - 1] - sum[sta.top()] + ans) % mod;
            sum[i] = (sum[i - 1] + dp[i]) % mod;
            ans = (ans + dp[i]) % mod;
            sta.push(i);
        }
//        for (int i = 1; i <= n; ++i) writesp(dp[i]);
//        puts("");
        writeln((ans + mod) % mod);
    }
    return 0;
}