4553: [Tjoi2016&Heoi2016]序列

Time Limit: 20 Sec??Memory Limit: 128 MB
Submit: 1202??Solved: 554
[Submit][Status][Discuss]

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

HINT

Source

用$mn_i$和$mx_i$表示$a_i$可能改變的最小/最大值，有$$j<i \& a_j \leq mn_i \& mx_j \leq a_i$$可以看出是三維偏序，CDQ分治解決。

1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 using namespace std; 5 6 const int N=100100; 7 int n,m,x,y,ans,c[N],f[N]; 8 struct P{ int a,mn,mx,x,y,id; }q[N],p[N]; 9 10 bool cmp(P a,P b){ return (a.x==b.x)?(a.y==b.y)?a.id<b.id:a.y<b.y:a.x<b.x; } 11 12 void add(int x,int k){ for (; x<=100000; x+=x&-x) c[x]=k?max(c[x],k):0; } 13 int que(int x){ int res=0; for (; x; x-=x&-x) res=max(res,c[x]); return res; } 14 15 void solve(int l,int r){ 16 if (l==r){ f[l]=max(f[l],1); return; } 17 int mid=(l+r)>>1; solve(l,mid); 18 rep(i,l,r) 19 if (q[i].id<=mid) p[i].x=q[i].a,p[i].y=q[i].mx,p[i].id=q[i].id; 20 else p[i].x=q[i].mn,p[i].y=q[i].a,p[i].id=q[i].id; 21 sort(p+l,p+r+1,cmp); 22 rep(i,l,r) if (p[i].id<=mid) add(p[i].y,f[p[i].id]); else f[p[i].id]=max(f[p[i].id],que(p[i].y)+1); 23 rep(i,l,r) if (p[i].id<=mid) add(p[i].y,0); 24 solve(mid+1,r); 25 } 26 27 int main(){ 28 freopen("bzoj4553.in","r",stdin); 29 freopen("bzoj4553.out","w",stdout); 30 scanf("%d%d",&n,&m); 31 rep(i,1,n) scanf("%d",&q[i].a),q[i].mn=q[i].mx=q[i].a,q[i].id=i; 32 rep(i,1,m) scanf("%d%d",&x,&y),q[x].mn=min(q[x].mn,y),q[x].mx=max(q[x].mx,y); 33 solve(1,n); 34 rep(i,1,n) ans=max(ans,f[i]); 35 printf("%d\n",ans); 36 return 0; 37 }

?

轉載于:https://www.cnblogs.com/HocRiser/p/8579553.html

總結

以上是生活随笔為你收集整理的[BZOJ4553][TJOI2016HEOI2016]序列(CDQ分治)的全部內容，希望文章能夠幫你解決所遇到的問題。

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