對于高度相同的一段可以合并，用鏈表從左往右維護這些連續段，每段維護以下信息：

$l,r$：表示區間的左右端點。

$t,a$：表示在第$t$天結束時它的高度是$a$。

$b$：當陽光在左邊時它是否會長高。

$c$：當陽光在右邊時它是否會長高。

令$sa[i],sb[i]$分別表示前$i$天中陽光在左/右邊的天數，那么顯然第$i$天這一段的高度為$a+b(sa[i]-sa[t])+c(sb[i]-sb[t])$。

對于相鄰的兩段，根據其$b$和$c$，可以得出它們合并的時間。

一天一天進行模擬，每天只處理那一天可能發生的合并事件，然后重新計算新的合并發生的時間即可。

時間復雜度$O(n+m)$。

?

#include<cstdio> const int N=300010,M=N*3; int n,m,ca,cb,i,j,k,T,h[N],tot;char b[N]; int sa[N],sb[N],ga[N],gb[N],gab[N],v[M],nxt[M],ed; struct P{int l,r,pre,nxt,t,a;bool b,c,del;}e[N]; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} inline void add(int&x,int y){v[++ed]=y;nxt[ed]=x;x=ed;} inline int ask(const P&p){return p.a+p.b*(ca-sa[p.t])+p.c*(cb-sb[p.t]);} inline void cal(P&p){p.b=ask(p)<ask(e[p.pre]);p.c=ask(p)<ask(e[p.nxt]); } inline void merge(int o); inline void check(int o){P&p=e[o],&q=e[p.nxt];int x=ask(p),y=ask(q),z=x<y?y-x:x-y;if(!z)merge(o);bool fa=(x>y)^p.b,fb=(x<y)^q.c;if(fa&&fb){if(ca+cb+z<=m)add(gab[ca+cb+z],o);return;}if(fa){if(ca+z<=m)add(ga[ca+z],o);return;}if(fb){if(cb+z<=m)add(gb[cb+z],o);return;} } inline void merge(int o){P&p=e[o];if(p.del||!p.nxt)return;P&q=e[p.nxt];int x=ask(p),y=ask(q);if(x!=y)return;q.del=1;p.r=q.r;p.nxt=q.nxt;if(q.nxt)e[q.nxt].pre=o;p.t=T,p.a=x;cal(p);if(p.pre)check(p.pre);if(p.nxt)check(o); } int main(){read(n),read(m);for(i=1;i<=n;i++)read(h[i]);for(i=1;i<=n;i=j){for(j=i;j<=n&&h[i]==h[j];j++);tot++;e[tot].l=i,e[tot].r=j-1;e[tot].a=h[i];}for(i=1;i<tot;i++)e[i].nxt=i+1;for(i=2;i<=tot;i++)e[i].pre=i-1;for(i=1;i<=tot;i++)cal(e[i]);for(i=1;i<tot;i++)check(i);scanf("%s",b+1);for(T=1;T<=m;T++){b[T]=='A'?ca++:cb++;sa[T]=sa[T-1]+(b[T]=='A');sb[T]=sb[T-1]+(b[T]=='B');for(j=ga[ca];j;j=nxt[j])merge(v[j]);for(j=gb[cb];j;j=nxt[j])merge(v[j]);for(j=gab[T];j;j=nxt[j])merge(v[j]);ga[ca]=gb[cb]=0;}for(i=1;i<=tot;i++)if(!e[i].del)for(k=ask(e[i]),j=e[i].l;j<=e[i].r;j++)h[j]=k;for(i=1;i<=n;i++)printf("%d%c",h[i],i<n?' ':'\n');return 0; }

　　

轉載于:https://www.cnblogs.com/clrs97/p/6545482.html

總結

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

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