題意：排列的極長上升子序列個數

$n\le 2\times 10^5$

顯然有個 dp

$$f_n=\sum _{i<n,p_i<p_n,?i<j<n\text{?s.t.?}{p}_i<p_j<p_n}{f}_i$$

相當于要對 $i<n,p_i<p_n$ 維護一個單調棧。

這樣并不好搞，但我們換個角度，每個 $i$ 產生貢獻的 $n$ 也是關于 $p_i$ 的單調棧的形式。

（仔細想想好像不是單調棧，感性理解好了）

考慮怎么維護這東西。用一棵權值線段樹來維護當前每個位置的棧頂的值。

添加一個數 $v$ 時，視為在所有 $p_i<v$ 的棧 $i$ 中壓入了 $v$，相當于是對 $[1,v]$ 取 $\min$ 。

然后棧頂值為 $v$ 的位置可以產生貢獻，用最大值判一下就可以了。

最后這個位置新開一個棧，即把 $v$ 改成 $+\infty$，并把貢獻放到樹上。

用 SGB 維護即可。

因為只有單點修改，所以復雜度為 $O(n\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 200005 using 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|1 struct 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; }

總結

以上是生活随笔為你收集整理的【牛客NOIP模拟】牛半仙的妹子序列【DP】【Segment Tree Beats】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。