#Description

佳媛姐姐過生日的時候，她的小伙伴從某寶上買了一個有趣的玩具送給他。玩具上有一個數列，數列中某些項的值

可能會變化，但同一個時刻最多只有一個值發生變化。現在佳媛姐姐已經研究出了所有變化的可能性，她想請教你
，能否選出一個子序列，使得在任意一種變化中，這個子序列都是不降的？請你告訴她這個子序列的最長長度即可
。注意：每種變化最多只有一個值發生變化。在樣例輸入1中，所有的變化是：
1 2 3
2 2 3
1 3 3
1 1 31 2 4
選擇子序列為原序列，即在任意一種變化中均為不降子序列在樣例輸入2中，所有的變化是:3 3 33 2 3選擇子序列
為第一個元素和第三個元素，或者第二個元素和第三個元素，均可滿足要求
#Input

輸入的第一行有兩個正整數n, m，分別表示序列的長度和變化的個數。接下來一行有n個數，表示這個數列原始的

狀態。接下來m行，每行有2個數x, y，表示數列的第x項可以變化成y這個值。1 <= x <= n。所有數字均為正整數
，且小于等于100,000
#Output

輸出一個整數，表示對應的答案

#Sample Input

3 4

1 2 3

1 2

2 3

2 1

3 4
#Sample Output

3

#Solution

• 有一個序列，每個位置的值可能會變。

• 題目要求無論怎么變都是不下降子序列的最大長度。

• 一個顯然的DP，設 $f[i]$ 表示以 $i$ 結尾的最長不下降子序列長度，則：$$f[i]=max(f[j])+1(j\le i)$$

• 其中 $j$ 滿足以下兩個條件（$mx[i],mn[i]$ 分別表示 $i$ 號點變化的最大值和最小值）：

$a[j]\le mn[i]$

$mx[j]\le a[i]$

• 如何優化DP呢？考慮cdq分治。

• 構造遞歸過程 $solve(l,r)$ 表示處理區間 $[l,r]$ 的答案。

• 那么先執行 $solve(l,mid)(mid=(l+r)/2)$ 。

• 于是我們可以通過左邊計算右邊的答案。

• 將區間 $[l,mid]$ 的 $a$ 值從小到大排序，區間 $[mid+1,r]$ 的 $mn$ 值從小到大排序。

• 用指針維護，先滿足條件①：$a[j]\le mn[i]$

• 再將滿足條件的 $j$ 的 $f[j]$ 加到 $mx[j]$ 位置的樹狀數組里。

• 之后 $f[i]$ 從區間 $[1,a[i]]$ 中查找最大值轉移即可，這樣又滿足了條件②：$mx[j]\le a[i]$ 。

• 這樣就成功實現了從左邊轉移到右邊的 $f$ 值。

• 那從右邊轉移右邊的呢？這時再執行 $solve(mid+1,r)$ 即可。

• 要記得在 $solve(mid+1,r)$ 前清空樹狀數組。

• cdq分治+樹狀數組，時間復雜度 $O(Nlo{g}^{2}N)$ 。

#Code

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; const int N=1e5+5; int num,ans; int a[N],mx[N],mn[N],id[N],f[N],g[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline bool cmpa(int x,int y) {return a[x]<a[y]; } inline bool cmpmn(int x,int y) {return mn[x]<mn[y]; } inline void change(int x,int y) {while(x<=num) g[x]=y?max(g[x],y):0,x+=x&-x; } inline int query(int x) {int sum=0;while(x) sum=max(sum,g[x]),x-=x&-x;return sum; } void solve(int l,int r) {if(l==r){f[l]=max(f[l],1);return;}int mid=l+r>>1;solve(l,mid);for(int i=l;i<=r;i++) id[i]=i;sort(id+l,id+1+mid,cmpa);sort(id+mid+1,id+1+r,cmpmn);int j=l;for(int i=mid+1;i<=r;i++){while(j<=mid && a[id[j]]<=mn[id[i]]) change(mx[id[j++]],f[id[j]]);f[id[i]]=max(f[id[i]],query(a[id[i]])+1);}for(int i=l;i<j;i++) change(mx[id[i]],0);solve(mid+1,r); } int main() {int n=read(),m=read();for(int i=1;i<=n;i++) mx[i]=mn[i]=a[i]=read();while(m--){int x=read(),y=read();mx[x]=max(mx[x],y);mn[x]=min(mn[x],y);}for(int i=1;i<=n;i++) num=max(num,mx[i]);solve(1,n);for(int i=1;i<=n;i++) ans=max(ans,f[i]);printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 4553: [Tjoi2016Heoi2016]序列的全部內容，希望文章能夠幫你解決所遇到的問題。

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