Largest Rectangle in a Histogram

ps：单调栈，注意红色部分的代码。

int n;stack<P> s;inline void upd(LL &x, LL y) { (x < y) && (x = y); }int main()
{while(sc(n) != EOF && n) {while(!s.empty()) s.pop();LL ans = 0;Rep(i, 1, n) {int x;sc(x);if (s.empty()) s.push(P(x, i));else if (x > s.top().first) s.push(P(x, i));else if (x == s.top().first) {P res = P(x, s.top().second);s.pop();s.push(res);}else {int pos;while(s.top().first > x) {P tp = s.top();s.pop();pos = tp.second;
                upd(ans, 1ll * (i - tp.second) * tp.first);if (s.empty()) break;}s.push(P(x, pos));
        }}while(!s.empty()) {P tp = s.top();s.pop();upd(ans, 1ll * (n + 1 - tp.second) * tp.first);}pr(ans);}return 0;
}