正題

題目鏈接:https://www.luogu.com.cn/problem/P4309

---

題目大意

$n$次，第$i$次在第$x_i$個數(shù)字后面插入$i$然后詢問最長上升子序列長度。

---

解題思路

因為是插入所以考慮用$Splay$維護，因為從小到大插入，其實每次就是找一個在$x_i$前面最大的$f_i$就好了，這個也用$Splay$維護即可。

時間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,cnt,root,f[N],g[N],ans; int t[N][2],fa[N],siz[N]; bool Direct(int x) {return t[fa[x]][1]==x;} void Connect(int x,int y,int dir) {t[x][dir]=y;fa[y]=x;return;} void PushUp(int x){g[x]=max(max(g[t[x][0]],g[t[x][1]]),f[x]);siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return; } void Rotate(int x){int y=fa[x],z=fa[y];int xs=Direct(x),ys=Direct(y);int w=t[x][xs^1];Connect(z,x,ys);Connect(y,w,xs);Connect(x,y,xs^1);PushUp(y);PushUp(x);return; } void Splay(int x,int f){while(fa[x]!=f){int y=fa[x];if(fa[y]==f)Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}if(!f)root=x;return; } int Find(int x,int k){if(siz[t[x][0]]>=k)return Find(t[x][0],k);if(siz[t[x][0]]+1==k)return x;return Find(t[x][1],k-siz[t[x][0]]-1); } int main() {scanf("%d",&n);t[2][0]=siz[1]=siz[2]=1;fa[1]=root=cnt=2;for(int i=1;i<=n;i++){int k;scanf("%d",&k);int x=Find(root,k+1),y=Find(root,k+2);Splay(y,0);Splay(x,y);t[x][1]=++cnt;fa[cnt]=x;f[cnt]=g[cnt]=g[x]+1;siz[cnt]=1;ans=max(ans,f[cnt]);printf("%d\n",ans);PushUp(x);PushUp(y);Splay(cnt,0);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P4309-[TJOI2013]最长上升子序列【Splay】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。