提出 #72210073

---

ソースコード 拡げる

#include <bits/stdc++.h>
#pragma GCC optimize("O3,fast-math")
using namespace std;
typedef long long ll;
#define int ll
int tc,n,a[303030];
const int mod=998244353;
struct Node1{
    int cnt[3][3]; // x-y, wmdrka
    Node1() {
        memset(cnt,0,sizeof(cnt));
    }
    Node1(int q,int w,int e,int r,int t,int y,int u,int i,int o) {
        cnt[0][0]=q;
        cnt[0][1]=w;
        cnt[0][2]=e;
        cnt[1][0]=r;
        cnt[1][1]=t;
        cnt[1][2]=y;
        cnt[2][0]=u;
        cnt[2][1]=i;
        cnt[2][2]=o;
    }
};
struct seg{
    using Node = Node1;
    int n,lg,SZ; vector<Node> tree;
    seg(int sz) {
        n=sz; SZ=1; lg=0; while (SZ<n) {SZ<<=1; lg++;}
        tree.resize(2*SZ+5);
    }
    void set(int ind, Node val) {
        --ind|=SZ; tree[ind]=val;
    }
    Node merge(Node a, Node b) {
        Node ret;
        for(int i=0;i<3;i++) for(int j=0;j<3;j++) ret.cnt[i][j]=(a.cnt[i][j]+b.cnt[i][j])%mod;
        return ret;
    }
    void init() {
        for(int i=SZ-1;i;i--) tree[i]=merge(tree[i<<1],tree[i<<1|1]);
    }
    void pull(int ind) {
        tree[ind]=merge(tree[ind<<1], tree[(ind<<1)|1]);
    }
    void upd(int ind, Node val) {
        --ind|=SZ; tree[ind]=merge(tree[ind],val);
        for(ind>>=1;ind;ind>>=1) pull(ind);
    }
    Node qry(int l, int r) {
        Node nl,rr; --l|=SZ; --r|=SZ;
        for(;l<=r;l>>=1,r>>=1) {
            if(l&1) nl=merge(nl,tree[l++]);
            if(~r&1) rr=merge(tree[r--],rr);
        }
        return merge(nl,rr);
    }
};

void solve() {
    cin >> n;
    if(n<3) {cout << 0; return;}
    for(int i=1;i<=n;i++) cin >> a[i];
    seg t=seg(n);
    t.upd(a[1],Node1(0,0,0,0,1,0,0,0,0));
    for(int i=2;i<=n;i++) {
        t.upd(a[i],Node1(0,0,0,0,1,0,0,0,0));
        if(a[i]>1) {
            Node1 l=t.qry(1,a[i]-1);
            int q=(l.cnt[0][0]+l.cnt[0][1]+l.cnt[0][2]+l.cnt[1][2])%mod;
            int w=(l.cnt[1][0]+l.cnt[1][1]+l.cnt[2][2])%mod;
            int e=(l.cnt[2][0]+l.cnt[2][1])%mod;
            Node1 cur=Node1(q,0,0,w,0,0,e,0,0);
            t.upd(a[i],cur);
        }
        if(a[i]<n) {
            Node1 l=t.qry(a[i]+1,n);
            int q=(l.cnt[0][1]+l.cnt[0][2])%mod;
            int w=(l.cnt[1][1]+l.cnt[1][2]+l.cnt[0][0])%mod;
            int e=(l.cnt[2][0]+l.cnt[2][1]+l.cnt[2][2]+l.cnt[1][0])%mod;
            Node1 cur=Node1(0,0,q,0,0,w,0,0,e);
            t.upd(a[i],cur);
        }
    }
    auto last=t.qry(1,n);
    //cout << last.cnt[2][0] << last.cnt[2][1] << last.cnt[2][2] << "\n";
    cout << (last.cnt[2][0]+last.cnt[2][1]+last.cnt[2][2])%mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(tc=1;tc;tc--) {
        solve();
    }
}

提出情報

ジャッジ結果