C++14(g++5.4) 解法, 执行用时: 203ms, 内存消耗: 25888K, 提交时间: 2020-09-25 22:31:22

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
const int maxn = 1001001;
int f[maxn], g[maxn], h[maxn], sh[maxn], s[maxn], s2[maxn], sj[maxn], r[maxn], id[maxn];
struct node {
    int v, id;
    bool operator < (const node & a) const {
        return v < a.v || (v == a.v && id > a.id);
    }
} p[maxn];
int main(void) {
    //freopen("e.in","r",stdin);
    int n; scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&p[i].v), p[i].id=i;
    for (int i=n+1;i<=n+n;i++) p[i].v=p[i-n].v+1, p[i].id=i-n;
    sort(p+1,p+n+n+1);

    for (int i=1,tot=0;i<=2*n;i++) {
        if (!id[p[i].id]) id[p[i].id] = ++tot;
        else r[id[p[i].id]] = tot;
    }

//    for (int i=1;i<=n;i++) printf("%d ",r[i]); puts("");
    f[n] = g[n] = s[n] = s2[n] = 1;
    sj[n] = n;
    for (int i=n-1;i>=1;i--) {
        f[i] = (f[i+1] + (sh[i+2] - sh[r[i+1]+1] + mod)%mod)%mod;
        if (r[i] == i+1) h[i+1] = f[i+1];
        else if (r[i] >= i+2) {
            h[i+1] = (((f[i+1] + (sj[i+2]-sj[r[i]]+mod)%mod)%mod - (i+1)*(ll)(s2[i+2]-s2[r[i]]+mod)%mod + mod)%mod
                + (r[i]-(i+1))*(ll)g[r[i]]%mod)%mod;
        }
        sh[i+1] = (h[i+1] + sh[i+2])%mod;
        s[i] = (sh[max(i+2,r[i]+1)] - sh[r[i+1]+1] + mod)%mod;
        if (r[i] == i) g[i] = f[i];
        else g[i] = (g[i+1] + s[i])%mod;
        s2[i] = (s[i] + s2[i+1])%mod;
        sj[i] = (i*(ll)s[i]%mod + sj[i+1])%mod;
//        printf("f[%d] = %d\n",i,f[i]);
//        printf("h[%d] = %d\n",i+1,h[i+1]);
//        printf("g[%d] = %d\n",i,g[i]);
//        printf("s[%d] = %d\n",i,s[i]);
    }
    int ans = (f[1] + (sh[2] - sh[r[1]+1] + mod)%mod)%mod;
    printf("%d\n", ans);
    return 0;
}

C++(clang++11) 解法, 执行用时: 130ms, 内存消耗: 6288K, 提交时间: 2021-02-08 10:43:10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,mod=998244353;
int n,f[N];
struct node
{
    int x,id;
    bool operator<(const node&o)const
    {
        return x==o.x?id<o.id:x>o.x;
    }
}a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+1+n);
    f[0]=1;
    for(int i=1,l=1,r=1;i<=n;i++)
    {
        f[i]=(f[i]+f[i-1]*2%mod)%mod;
        r=max(r,i);
        while(r<=n&&(a[r].x==a[i].x||a[r].x==a[i].x-1&&a[r].id<a[i].id)) r++;
        while(l<i&&(a[l].x>a[i].x+1||a[l].x==a[i].x+1&&a[l].id<a[i].id)) l++;
        f[r-1]=(f[r-1]+mod-f[l-1])%mod;
    }
    printf("%d\n",f[n]);
}