//感觉有必要把这题放博客上待复习 刚刚写解题报告的时候发现自己又不会做这题了
//我不会告诉你这题绝对是命题人抄poj2559
这题使用一个单调递增的栈，栈内存储的元素有两个值，一个高度，一个长度。
假如后一个元素的高度比栈顶元素小，那么从栈顶元素一定无法延伸到当前元素，于是乎我们就弹栈来降低栈顶的元素的高度，即把栈顶的元素和下一个元素合并，合并后高度为两者的最小值，宽度为两者加和（其实这就相当于新产生了一种方案）。进行弹栈操作直到栈顶元素小于当前元素，然后当前元素进栈。
弹栈时记录新产生的栈的元素的面积（其实就是新方案的面积），取最大值即为答案。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; struct rec{
int h,w;
}; int n;
rec a[];
rec stk[];
int top; int main(){
memset(a,,sizeof(a));
memset(stk,,sizeof(stk));
scanf("%d",&n);
for (int i=;i<=n;i++){
scanf("%d%d",&a[i].w,&a[i].h);
}
top=;
int ans=;
for (int i=;i<=n;i++){
int totw=;
while (top> && stk[top].h>a[i].h){
totw=totw+stk[top].w;
ans=max(ans,stk[top].h*totw);
top--;
}
top++;
stk[top].w=a[i].w+totw;
stk[top].h=a[i].h;
}
while (top>){
ans=max(ans,stk[top].h*stk[top].w);
stk[top-].w=stk[top-].w+stk[top].w;
top--;
}
printf("%d\n",ans);
}
/*
3
3 4
1 2
3 4 3
3 2
10 3
3 3 7
1 2
1 1
1 4
1 5
1 1
1 3
1 3
*/