2019 计蒜之道 复赛A. 外教 Michale 变身大熊猫(

标签（空格分隔）： 题解(计蒜客)

ps:计蒜之道复赛2题拿T-shirt.但是我好菜啊。只拿了一题

本题要求

#pragma GCC optimize("O2") 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x"=" << x << endl;
typedef long long LL;
int n;
const LL MOD = 998244353;
typedef pair<LL, LL> P;
#define len first
#define cnt second
#define val first
#define id second
const int MAX_N = 5*1e5+100;
const LL INF = 1e9;
P a[MAX_N];
P bit[MAX_N];
int dp[MAX_N];
P L[MAX_N], R[MAX_N];

void upd(P &a, P b){
    if(b.len > a.len){
        a = b;
    } else if(b.len == a.len){
        a.cnt = (a.cnt + b.cnt) % MOD;
    }
}

void add(int i, P p){
    while(i <= n){
        upd(bit[i], p);
        i += i & -i;    
    }
}

P query(int i){
    P res;
    while(i){
        upd(res, bit[i]);
        i -= i & -i;
    }
    return res;
}

bool cmp(P a, P b){
    return a.val < b.val || (a.val == b.val && a.id > b.id);
}

LL powN(LL base, int n){
    LL res = 1LL;
    while(n){
        if(n&1) res = res * base % MOD;
        base = base * base % MOD;
        n >>= 1;
    }
    return res;
} 

int main(){
    //freopen("in.txt","r",stdin);    
    ios::sync_with_stdio(0); cin.tie(0);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) dp[i] = INF;
    for(int i = 0; i < n; ++i){
        scanf("%lld", &a[i].val);
        *lower_bound(dp, dp+n, a[i].val) = a[i].val;
        a[i].id = i+1;
    }
    int mx = lower_bound(dp, dp+n, INF) - dp;
    sort(a, a+n, cmp);
    LL ans = 0;
    for(int i = 0; i < n; ++i){
        P p = query(a[i].id-1);
        if(++p.len == 1) p.cnt = 1;
        // p.len表示以当前作为结尾的上升序列的最大长度.p.cnt表示有多少个这样的序列 
        if(p.len == mx){
            ans = (ans + p.cnt) % MOD;
        }
        add(a[i].id, p);
        L[a[i].id] = p;
    }
    for(int i = 1; i <= n; ++i) {
        bit[i].len = 0;
        bit[i].cnt = 0;
    }
    for(int i = n-1; i >= 0; --i){
        P p = query(n-a[i].id);
        if(++p.len == 1) p.cnt = 1;
        add(n+1-a[i].id, p);
        R[a[i].id] = p;
    }
    LL q = powN(ans, MOD-2);
    for(int i = 1; i <= n; ++i){
        if(L[i].len + R[i].len == mx+1){
            printf("%lld ", L[i].cnt * R[i].cnt % MOD * q % MOD);
        } else printf("0 ");
    }
    putchar('\n');
    return 0;
}