TopCoder SRM 337 Div1 Medium BuildingAdvertise
問題
n本のビルがあり、それぞれのビルは幅1高さh[i]の長方形をしていて、
(i,0)を左下の頂点、(i+1,h[i])を右上の頂点としている。
このビルに収まる、軸に平行な長方形のうち、面積が最大のものの面積を求めよ。
制約条件
n≦100000
h[i]≦835454957
方針
典型問。蟻本280p
L[i]を、h[j]<h[i]となるようなj≦iの最大値
R[i]を、h[j]<h[i]となるようなj≧iの最小値とすると、
面積はmax((R[i]-L[i]-1)*h[i])となる。
L[i],R[i]はスタックを使ってO(n)で計算できる。
なんか蟻本の方針を思い出せなかったので、
スタックを使う+スタック上でh[j]<h[i]となるjを二分探索で探すというよくわからないことをやった。
ソースコード
int sz; ll r[100001],st[100001]; void init(vi &h,int n){ int j=0, m=h.size(); rep(i,n){ r[i+1]=h[j]; int s=(j+1)%m; h[j]=((h[j]^h[s])+13)%835454957; j=s; } } class BuildingAdvertise { public: long long getMaxArea(vector <int> h, int n) { init(h,n++); r[n++]=0; r[0]=0; ll ans=0; sz=0; rep(i,n){ while(sz&&r[st[sz-1]]>r[i]){ int lo=0,hi=sz,mid; while(lo+1<hi){ mid=(lo+hi)/2; if(r[st[mid]]<r[st[sz-1]])lo=mid; else hi=mid; } ans=max(ans,(i-st[lo]-1)*r[st[sz-1]]); sz--; } st[sz++]=i; } return ans; } };