单调栈

涉及任意区间（子序列）求最大最小值的一系列操作（可以求这个元素在那个区间是最小值 || 最大值）

向左向右的第一个比当前元素大的值（的下标等）

单调栈就行了

例题：

ZZULI XXX

题意：给你一串序列，要你求所有子序列的最小值之和。（n很大，无法暴力）

思路：完美的单调栈模板

这里简要介绍下单调栈的性质，(其他的都没用)

单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。

单调栈的性质：

1.单调栈里的元素具有单调性

2.元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除

3.使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。

求最小值用单调递增最大值用单调递减

（也就是说在元素进栈前他向左拓展的区间已经确定，在出栈前她能向右拓展的区间也能确定）（即这个元素在哪个区间是最小的（最大的））

#include<map>     
#include<stack>            
#include<queue>            
#include<vector>    
#include<string>  
#include<math.h>            
#include<stdio.h>            
#include<iostream>            
#include<string.h>            
#include<stdlib.h>    
#include<algorithm>   
#include<functional>    
using namespace std;
typedef long long  ll;
#define inf  1000000000       
#define mod 1000000007             
#define maxn  286000  
#define PI 3.1415926
#define lowbit(x) (x&-x)            
#define eps 1e-9  
struct node
{
    long long x, y, l, r;
}str[maxn];
stack<node>t;
int  main()
{
    long long  T, i, j, n, m, k, sum;
    scanf("%lld", &T);
    while (T--)
    {
        sum = 0;
        scanf("%lld", &n);
        for (i = 1;i <= n;i++)
        {
            scanf("%lld", &str[i].x);
            str[i].y = i;
        }
        for (i = 1;i <= n;i++)
        {
            str[i].l = i;
            while (t.empty() == 0 && t.top().x>str[i].x)
            {
                str[t.top().y].r = i - 1;
                str[i].l = str[t.top().y].l;
                t.pop();
            }
            t.push(str[i]);
        }
        while (t.empty() == 0)
        {
            str[t.top().y].r = n;
            t.pop();
        }
        for (i = 1;i <= n;i++)
            sum += str[i].x*(i - str[i].l + 1)*(str[i].r - i + 1);
        printf("%lld
", sum);
    }
}