SRM337 div1 medium

ALGORITHM NOTE ヒストグラム中の最大の長方形の面積
または
Amazon.co.jp： プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本
の280ページ、スタックの利用を参照。

#include <vector>
#include <stack>

using namespace std;
typedef long long LL;

class BuildingAdvertise 
{
	public:

		int n;
		vector<int> building;
		vector<int> L,R;

		void makeR(vector<int> h)
		{
			building=vector<int>(n,0);
			int j=0;
			int m=h.size();
			for(int i=0;i<n;i++)
			{
				building[i]=h[j];
				int s=(j+1)%m;
				h[j]=((h[j]^h[s])+13)%835454957;
				j=s;
			}
		}

		LL getMaxArea(vector <int> h, int _n) 
		{
			n=_n;
			makeR(h);

			L=vector<int>(n,0);
			R=vector<int>(n,0);

			stack<int> sta;
			for(int i=0;i<n;i++)
			{
				while(!sta.empty() && building[i]<=building[sta.top()])
					sta.pop();
				if(sta.empty())
					L[i]=0;
				else
					L[i]=sta.top()+1;
				sta.push(i);
			}
			while(!sta.empty())
				sta.pop();
			for(int i=n-1;0<=i;i--)
			{
				while(!sta.empty() && building[i]<=building[sta.top()])
					sta.pop();
				if(sta.empty())
					R[i]=n;
				else
					R[i]=sta.top();
				sta.push(i);
			}
			LL ans=0;
			for(int i=0;i<n;i++)
				ans=max(ans,(LL)(R[i]-L[i])*(LL)building[i]);
			return ans;

		}
};