正題

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

---

正題

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

---

題目大意

有一個長度為$n$的序列$a$，要求$a_i\in [l_i,r_i]$，要求使得$a$的最長嚴格上升子序列最長。

$1\le n\le 3\times 10^5,1\le l_i\le r_i\le 10^9$

---

解題思路

考慮一下暴力的做法，我們設$f_i$表示在目前的序列中后面加個數字$i$為結尾時的最長上升子序列，那么顯然$f$是單調不降的。

同理由于是嚴格上升，所以我們$f$不可能一次升$2$的值，也就是$f_i\le f_{i?1}+1$。所以我們可以考慮維護$f_i=f_{i?1}+1$的位置，也就是維護$f$的差分數組中的$1$的位置。

考慮新加入一個$[l,r]$時的變化，那對于所有$i\in [l+1,r+1]$都有$f_i=max\{f_i,f_j+1\}(j<i)$，注意到$1$位置的變化我們可以得出一下結論，當修改$[l,r]$時需要

將$[l+1,r]$中所有$1$的后面那個$1$移動到這個$1$的后一位。

將$[l+1,r]$中的第一個$1$移動到$l+1$處

這個操作看起來很難實現，實際上我們可以將第一個視為將$[l+1,r+1]$中的$1$往后移一格。

我們用FhqTreap維護$1$的位置，然后把$(r,\infty )$中第一個$1$刪除，$[l+1,r]$中的所有$1$往后移一格，再在$l+1$這個位置插一個$1$就好了。

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

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e5+10; int n,cnt,rt,w[N],dat[N],lazy[N],siz[N],t[N][2]; void Downdata(int x){if(!lazy[x])return;for(int i=0;i<2;i++){if(!t[x][i])continue;lazy[t[x][i]]+=lazy[x];w[t[x][i]]+=lazy[x];}lazy[x]=0;return; } int NewNode(int val){siz[++cnt]=1;dat[cnt]=rand();w[cnt]=val;return cnt; } void PushUp(int x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return; } void Split(int &x,int &y,int p,int k){if(!p){x=y=0;return;}Downdata(p);if(w[p]<=k)x=p,Split(t[x][1],y,t[p][1],k);else y=p,Split(x,t[y][0],t[p][0],k);PushUp(p);return; } int Merge(int x,int y){Downdata(x);Downdata(y);if(!x||!y)return x|y;if(dat[x]<dat[y]){t[x][1]=Merge(t[x][1],y);PushUp(x);return x;}else{t[y][0]=Merge(x,t[y][0]);PushUp(y);return y;}return x|y; } int Findk(int x,int k){if(siz[t[x][0]]>=k)return Findk(t[x][0],k);if(siz[t[x][0]]+1==k)return x;return Findk(t[x][1],k-siz[t[x][0]]-1); } int main() { // freopen("vague.in","r",stdin); // freopen("vague.out","w",stdout);srand(19260817);scanf("%d",&n);for(int i=1,l,r;i<=n;i++){scanf("%d%d",&l,&r);int x,y,z;l++;Split(x,y,rt,l-1);Split(y,z,y,r);if(z){int v=w[Findk(z,1)],nu;Split(nu,z,z,v);}if(y)lazy[y]++,w[y]++;y=Merge(NewNode(l),y);y=Merge(y,z);rt=Merge(x,y);}printf("%d\n",siz[rt]);return 0; }

總結

以上是生活随笔為你收集整理的CF809D-Hitchhiking in the Baltic States【FhqTreap】的全部內容，希望文章能夠幫你解決所遇到的問題。

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