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;
	}
};