题意：排列的极长上升子序列个数
n≤2×105n\leq 2\times 10^5n≤2×105
显然有个 dp
fn=∑i<n,pi<pn,∄i<j<ns.t.pi<pj<pnfif_n=\sum_{i<n,p_i<p_n,\nexists i<j<n\text{ s.t. }p_i<p_j<p_n}f_ifn=i<n,pi<pn,∄i<j<ns.t.pi<pj<pn∑fi
相当于要对 i<n,pi<pni<n,p_i<p_ni<n,pi<pn 维护一个单调栈。
这样并不好搞，但我们换个角度，每个 iii 产生贡献的 nnn 也是关于 pip_ipi 的单调栈的形式。
（仔细想想好像不是单调栈，感性理解好了）
考虑怎么维护这东西。用一棵权值线段树来维护当前每个位置的栈顶的值。
添加一个数 vvv 时，视为在所有 pi<vp_i<vpi<v 的栈 iii 中压入了 vvv，相当于是对 [1,v][1,v][1,v] 取 min\minmin 。
然后栈顶值为 vvv 的位置可以产生贡献，用最大值判一下就可以了。
最后这个位置新开一个栈，即把 vvv 改成 +∞+\infin+∞，并把贡献放到树上。
用 SGB 维护即可。
因为只有单点修改，所以复杂度为 O(nlogn)O(n\log n)O(nlogn)
#include <iostream>#include <cstdio>#include <cstring>#include <cctype>#define MAXN 200005using namespace std;const int MOD=998244353,INF=0x3f3f3f3f;inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;}inline int read(){int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;}int f[MAXN];#define lc p<<1#define rc p<<1|1struct node{int mx,se,sum;}t[MAXN<<2];int lzy[MAXN<<2];inline node merge(node a,node b){if (a.mx==b.mx)a.se=max(a.se,b.se),a.sum=add(a.sum,b.sum);else{if (a.mx<b.mx) swap(a,b);a.se=max(a.se,b.mx);}return a;}inline void pushlzy(int p,int v){t[p].mx=min(t[p].mx,v),lzy[p]=min(lzy[p],v);}inline void pushdown(int p){if (lzy[p]<INF){pushlzy(lc,lzy[p]),pushlzy(rc,lzy[p]);lzy[p]=INF;}}void modify(int p,int l,int r,int k,int v){if (l==r) return (void)(t[p].mx=INF,t[p].sum=v);int mid=(l+r)>>1;pushdown(p);if (k<=mid) modify(lc,l,mid,k,v);else modify(rc,mid+1,r,k,v);t[p]=merge(t[lc],t[rc]);}void modify(int p,int l,int r,int ql,int qr,int v){if (ql<=l&&r<=qr&&v>t[p].se) return pushlzy(p,v);if (qr<l||r<ql) return;int mid=(l+r)>>1;pushdown(p);modify(lc,l,mid,ql,qr,v),modify(rc,mid+1,r,ql,qr,v);t[p]=merge(t[lc],t[rc]);}node ans;void query(int p,int l,int r,int ql,int qr){if (ql<=l&&r<=qr){if (ql==l) ans=t[p];else ans=merge(ans,t[p]);return;}if (qr<l||r<ql) return;pushdown(p);int mid=(l+r)>>1;query(lc,l,mid,ql,qr),query(rc,mid+1,r,ql,qr);}int main(){memset(lzy,0x3f,sizeof(lzy));int n=read();for (int i=1;i<=n;i++){int v=read();modify(1,1,n,1,v,v),query(1,1,n,1,v);f[i]=(ans.mx==v? ans.sum:0);if (!f[i]) f[i]=1;modify(1,1,n,v,f[i]);}printf("%d\n",t[1].sum);return 0;}
