题目链接
题意：本题就是很显然的题意，让你求出共有多少个最长上升子序列，每个数在多少个最长上升子序列中。
这题的难点在于如何求出每个数在多少最长上升子序列中，显然可以用dp，直接dp时间复杂度不允许，由于我们只在前缀上转移，于是我们可以用树状数组优化dp，考虑一个结构体数组，有两个值，一个为以当前数结尾的最长上升子序列长度，一个是数量，我们每次遍历a数组（即输入的数组），查询在以 [ 1 , a t h − 1 ] [1,a_{th}-1] [1,ath​−1]这个范围结尾的LIS最长长度和数量。即可以推出以这个数结尾的LIS长度和数量，然后再反着做一遍，中间记录整个数组的LIS，记为L.,然后遍历整个数组，设当前为x，则假如 L I S 正 + L I S 反 = L + 1 LIS_正+LIS_反=L+1 LIS正​+LIS反​=L+1即这个数有在 c n t 正 ∗ c n t 反 cnt_正*cnt_反 cnt正​∗cnt反​个LIS中。输出一下就好啦
细节见代码。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 5e5 +11;
const LL mod=998244353;
LL n,a[N],b[N],fa[N],fb[N],ga[N],gb[N],M;
struct uzi
{
	LL a,b;//length,number
}t[N],le[N],ri[N];
uzi g(int x){
	uzi res;
	res.a=res.b=0;
	int ma=0,cnt=0;
	for(;x;x-=x&-x){
		if(t[x].a==ma){
			cnt=cnt+t[x].b;
			cnt%=mod;
		}else if(t[x].a>ma){
			ma=t[x].a;
			cnt=t[x].b;
		}
	}
	return uzi{ma,cnt};
}
void add(int x,uzi k){
	for(;x<N;x+=x&-x){
		if(t[x].a==k.a)t[x].b+=k.b,t[x].b%=mod;
		else if(t[x].a<k.a){t[x]=k;}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	for(int i=1;i<=n;i++){
		le[i]=g(a[i]-1);
		if(++le[i].a==1)le[i].b=1;
		add(a[i],le[i]);
		M=max(M,le[i].a);
	}
	memset(t,0,sizeof t);
	for(int i=1;i<=n;i++)a[i]=n-a[i]+1;
	for(int i=n;i>=1;i--){
		ri[i]=g(a[i]-1);
		if(++ri[i].a==1)ri[i].b=1;
		add(a[i],ri[i]);	
	}
	LL res=0;
	for(int i=1;i<=n;i++)if(le[i].a==M)res+=le[i].b,res%=mod;
	res=powmod(res,mod-2,mod);
	for(int i=1;i<=n;i++){
		if(le[i].a+ri[i].a==M+1)cout<<le[i].b*ri[i].b%mod*res%mod<<' ';
		else cout<<0<<' '; 
	}
	return 0;
}