传送门

就是求极长上升子序列的方案数，然而写了一下午加一晚上……
记着什么时候再打一遍这个板子，顺便把这题做了……

其实和God Knows类似，但之前线段树维护单调栈的板子没选好，可迁移性不高，现在回来填坑了
首先可以发现可以给每个点挂载一个方案数信息，就可以DP了
考虑如何优化，发现能产生贡献的点满足权值单调递减，所以问题可以转化成

• 在给定序列中，求所有满足\(j \leqslant i, a[j] \leqslant a[i]\)且单调递增/减的\(a[j]\)之和/最大值/最小值

就是线段树维护单调栈的典型问题了
首先用一个技巧处理掉\(a[j] \leqslant a[i]\)的限制：翻转坐标系，换成以\(a[i]\)为下标
那这样线段树中的点j一定满足\(j \leqslant i\)，而且可以用区间查询满足\(a[j] \leqslant a[i]\)的限制了，而且单调性不变
接下来就是线段树维护单调栈的板子了：

int calc(int p, int val) {
	if (tl(p)==tr(p)) return maxn(p)>=val?sum(p):0;
	int mid=(tl(p)+tr(p))>>1;
	if (maxn(p<<1|1)>=val) return (rec(p)+calc(p<<1|1, val))%mod;
	else return calc(p<<1, val);
}
void pushup(int p) {
	maxn(p)=max(maxn(p<<1), maxn(p<<1|1));
	rec(p)=calc(p<<1, maxn(p<<1|1));
}
int query(int p, int l, int r) {
	if (p==1) nowmax=0;
	if (l<=tl(p)&&r>=tr(p)) {
		if (tl(p)==tr(p)) return sum(p)>=nowmax?sum(p):0;
		int t=calc(p, nowmax);
		nowmax=max(nowmax, maxn(p));
		return t;
	}
	int mid=(tl(p)+tr(p))>>1, ans=0;
	if (r>mid) ans=(ans+query(p<<1|1, l, r))%mod;
	if (l<=mid) ans=(ans+query(p<<1, l, r))%mod;
	return ans;
}

剩下的细节见@Yubai的优秀讲解吧……

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f
#define N 200010
#define ll long long 
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline ll read() {
	ll ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n;
ll a[N], dp[N], lim[N], ans;
const ll mod=998244353;
bool vis[N];

namespace force{
	void solve() {
		for (int i=1; i<=n; ++i) a[i]=read();
		for (int i=2; i<=n; ++i) {
			for (int j=1; j<i; ++j) if (a[j]<a[i] && (!lim[j]||lim[j]>=a[i])) {
				dp[i]+=dp[j]?dp[j]:1ll, dp[i]%=mod;
				lim[j]=a[i];
			}
		}
		//cout<<"dp: "; for (int i=1; i<=n; ++i) cout<<dp[i]<<' '; cout<<endl;
		//cout<<"lim: "; for (int i=1; i<=n; ++i) cout<<lim[i]<<' '; cout<<endl;
		for (int i=1; i<=n; ++i) if (!lim[i]) ans+=dp[i]?dp[i]:1ll, ans%=mod;
		printf("%lld\n", ans);
		exit(0);
	}
}

namespace task{
	const int SIZE=N<<2;
	int tot, tl[SIZE], tr[SIZE]; ll sum[SIZE], maxn[SIZE], rec[SIZE], nowmax;
	#define tl(p) tl[p]
	#define tr(p) tr[p]
	#define sum(p) sum[p]
	#define maxn(p) maxn[p]
	#define rec(p) rec[p]
	int calc(int p, int val) {
		if (tl(p)==tr(p)) return maxn(p)>=val?sum(p):0;
		int mid=(tl(p)+tr(p))>>1;
		if (maxn(p<<1|1)>=val) return (rec(p)+calc(p<<1|1, val))%mod;
		else return calc(p<<1, val);
	}
	void pushup(int p) {
		maxn(p)=max(maxn(p<<1), maxn(p<<1|1));
		rec(p)=calc(p<<1, maxn(p<<1|1));
	}
	int query(int p, int l, int r) {
		if (p==1) nowmax=0;
		if (l<=tl(p)&&r>=tr(p)) {
			if (tl(p)==tr(p)) return sum(p)>=nowmax?sum(p):0;
			int t=calc(p, nowmax);
			nowmax=max(nowmax, maxn(p));
			return t;
		}
		int mid=(tl(p)+tr(p))>>1, ans=0;
		if (r>mid) ans=(ans+query(p<<1|1, l, r))%mod;
		if (l<=mid) ans=(ans+query(p<<1, l, r))%mod;
		return ans;
	}
	void build(int p, int l, int r) {
		tl(p)=l; tr(p)=r; 
		if (l==r) return ;
		int mid=(l+r)>>1;
		build(p<<1, l, mid);
		build(p<<1|1, mid+1, r);
		pushup(p);
	}
	void upd(int p, int pos, int val, int dat) {
		//cout<<"upd "<<p<<' '<<pos<<' '<<val<<' '<<dat<<endl;
		if (tl(p)==tr(p)) {maxn(p)=val; sum(p)=dat%mod; return ;}
		int mid=(tl(p)+tr(p))>>1;
		if (pos<=mid) upd(p<<1, pos, val, dat);
		else upd(p<<1|1, pos, val, dat);
		pushup(p);
	}
	void solve() {
		int t;
		for (int i=1; i<=n; ++i) a[i]=read()+1;
		build(1, 1, n+1);
		upd(1, a[1], 1, 1);
		for (int i=2; i<=n; ++i) {
			t = query(1, 1, a[i]);
			//cout<<i<<": "<<t<<endl;
			if (!t) t=1;
			upd(1, a[i], i, t);
		}
		nowmax=0;
		printf("%d\n", query(1, 1, n+1));
		exit(0);
	}
}

signed main()
{
	n=read();
	//force::solve();
	task::solve();
	
	return 0;
}