#include 
  
   
#include 
   
     using namespace std; const int N = 100005; struct Elem { long long height; long long width; int begin; int count; }; Elem stack[N]; int top; int main() { int num, n; long long ans, tmp, tot; int ansbeg, ansend, count; scanf("%d", &n); top = 0; ans = 0; ansbeg = ansend = 1; for (int i = 0; i < n; ++i) { scanf("%d", &num); tmp = 0; count = 0; while (top > 0 && stack[top - 1].width >= num) { stack[top - 1].count += count; tot = (stack[top - 1].height + tmp) * stack[top - 1].width; if (tot > ans) { ans = tot; ansbeg = stack[top - 1].begin; ansend = ansbeg + stack[top - 1].count - 1; } tmp += stack[top - 1].height; count = stack[top - 1].count; --top; } stack[top].height = num + tmp; stack[top].width = num; stack[top].begin = i + 1 - count; stack[top].count = 1 + count; ++top; } tmp = 0; count = 0; while (top > 0) { stack[top - 1].count += count; tot = (stack[top - 1].height + tmp) * stack[top - 1].width; if (tot > ans) { ans = tot; ansbeg = stack[top - 1].begin; ansend = ansbeg + stack[top - 1].count - 1; } tmp += stack[top - 1].height; count = stack[top - 1].count; --top; } printf("%lld\n%d %d\n", ans, ansbeg, ansend); return 0; }
   
  

题解：给定一个数组，定义某个区间的参考值为：区间所有元素的和*区间最小元素。求该数组中的最大参考值以及对应的区间。

解题报告：（1）设某个区间所有元素的和为height，区间最小元素为width，则对于单个元素的区间，height = width = 元素的值。建立一个单调递增的栈。

（2）栈中的每一个元素的height值等于前面比其大的和自身值的和；从第一个元素开始入栈，每个元素入栈之前必须先从栈顶开始删除大于或等于它的元素，把删除的所有元素的height累加到当前元素的height，然后把当前元素的值保存在width值中，这表示把当前元素前面比它大或相等的连续元素的值加起来，乘以它自己，也就是这段区间的参考值。

（3）每一次删除元素都需要计算一个参考值，取参考值的最大值就是答案了。不过题目还要求给出对应区间的起点和终点，因此在栈的操作过程中还得记录当前元素保存的区间的起点和大小，在更新参考值的过程中顺便更新区间的起点和终点就可以了。

#include 
  
   
using namespace std;

const int maxn = 80005;
int stack[maxn],top = 0;//top指向当前元素下一个位置

int main()
{
    long long ans = 0;
    int i,n,tmp;
    cin >> n;
    for(i=0;i
   
    > tmp; while(top>0 && stack[top-1]<=tmp) { top--; } ans += top; stack[top++] = tmp; } cout << ans << endl; }
   
  

题意：一群高度不完全相同的牛从左到右站成一排，每头牛只能看见它右边的比它矮的牛的发型，若遇到一头高度大于或等于它的牛，则无法继续看到这头牛后面的其他牛。给出这些牛的高度，要求每头牛可以看到的牛的数量的和。

解题报告：（1）把要求作一下转换，其实就是要求每头牛被看到的次数之和。这个可以使用单调栈来解决。

（2）从左到右依次读取当前牛的高度，从栈顶开始把高度小于或等于当前牛的高度的那些元素删除，此时栈中剩下的元素的数量就是可以看见当前牛的其他牛的数量。把这个数量加在一起，就可以得到最后的答案了。