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;
}