POJ 2082 Terrible Sets(单调栈)

题目链接：
POJ 2082 Terrible Sets
题意：
【题目描述成这样也是醉了。。。】
实际上就是给出$n$个并排矩形的底和高，求能划分的最大矩形面积。
数据范围：$n\leq 5*10^4$
分析；
和前面那道题其实一样的，只要用一个$sum[]$数组记录下底的和就好了。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 50010;int n;
ll height[MAX_N], width[MAX_N], sum[MAX_N];
int L[MAX_N], R[MAX_N], sta[MAX_N];//维护单调非递减栈
int main()
{while (~scanf("%d", &n)) {if(n == -1) break;sum[0] = 0;for (int i = 1; i <= n; ++i) {scanf("%lld%lld", &width[i], &height[i]);sum[i] = sum[i - 1] + width[i];}height[n + 1] = 0, sum[n + 1] = sum[n];int top = 0, cur;sta[0] = 0;for (int i = 1; i <= n + 1; ++i) {while(1) {cur = sta[top];if (height[cur] <= height[i]) break;R[cur] = i;top--;}L[i] = cur;sta[++top] = i;}ll ans = 0;for (int i = 1; i <= n; ++i) {ll len = sum[R[i] - 1] - sum[L[i]];//printf("L[%d] = %d R[%d] - 1 = %d\n", i, L[i], i, R[i] - 1);ans = max(ans, len * height[i]);}printf("%lld\n", ans);}return 0;
}