This documentation is automatically generated by competitive-verifier/competitive-verifier
ヒストグラム上の最大矩形の面積を求める.
largest_histogram_rectangle(v)
:幅 $1$ で高さ $v[i]$ のヒストグラム上に存在する最大矩形の面積を返す.#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> long long largest_histogram_rectangle(vector<T> &v) {
v.emplace_back(0);
int n = v.size();
long long mxrec = 0;
stack<pair<T, int>> s;
for(int i = 0; i < n; i++) {
int ni = i;
while(s.size() > 0 and s.top().first > v[i]) {
long long h = s.top().first, w = i - s.top().second;
long long rec = h * w;
if(mxrec < rec) mxrec = rec;
ni = s.top().second;
s.pop();
}
s.emplace(v[i], ni);
}
return mxrec;
}
#line 2 "dp/largest_histogram_rectangle.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> long long largest_histogram_rectangle(vector<T> &v) {
v.emplace_back(0);
int n = v.size();
long long mxrec = 0;
stack<pair<T, int>> s;
for(int i = 0; i < n; i++) {
int ni = i;
while(s.size() > 0 and s.top().first > v[i]) {
long long h = s.top().first, w = i - s.top().second;
long long rec = h * w;
if(mxrec < rec) mxrec = rec;
ni = s.top().second;
s.pop();
}
s.emplace(v[i], ni);
}
return mxrec;
}