题目描述
kkk做了一个人体感觉分析器。每一天，人都有一个感受值Ai，Ai越大，表示人感觉越舒适。在一段时间[i, j]内，人的舒适程度定义为[i, j]中最不舒服的那一天的感受值 * [i, j]中每一天感受值的和。现在给出kkk在连续N天中的感受值，请问，在哪一段时间，kkk感觉最舒适？
输入格式
第一行为N，代表数据记录的天数
第二行N个整数，代表每一天的感受值
输出格式
一行，表示在最舒适的一段时间中的感受值。
输入输出样例
输入 #1
6 3 1 6 4 5 2
输出 #1
60
说明/提示
样例解释：
kkk最开心的一段时间是第3天到第5天，开心值：(6+4+5)*4=60
对于30%的数据，1<=N<=100
对于70%的数据，1<=N<=2000
对于100%的数据，1<=N<=100000，1<=感受值<=1000000
分析
与这道题简直一模一样
这道题用区间的开头结尾做状态不太可行，但这道题对于区间还有一种状态，最值
好啦，这种题，我们可以发现对于某一个最小值，他的作用范围最大化可以使答案尽可能大
所以直接求出每一个最小值的作用范围就好
古人云，不贰过，不迁怒，但是我这个俗人已经在longlong上摔倒过n次了
还有，因为单调队列（单调栈）维护的是区间的最值，有单调性，所以取出来的数不一定是正好大于a[i]的数
这样就好
1 /************************ 2 User:Mandy.H.Y 3 Language:c++ 4 Problem:luogu2422 5 Algorithm: 6 ************************/ 7 #include<bits/stdc++.h> 8 9 using namespace std; 10 11 const int maxn = 1e5 + 5; 12 13 int n; 14 long long ans; 15 long long sum[maxn],a[maxn]; 16 int l,r,q[maxn]; 17 long long _left[maxn],_right[maxn]; 18 19 template<class T>inline void read(T &x){ 20 x = 0;bool flag = 0;char ch = getchar(); 21 while(!isdigit(ch)) flag |= ch == '-',ch = getchar(); 22 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar(); 23 if(flag) x = -x; 24 } 25 26 void file(){ 27 freopen("2422.in","r",stdin); 28 freopen("2422.out","w",stdout); 29 } 30 31 void readdata(){ 32 read(n); 33 } 34 35 void work(){ 36 for(int i = 1;i <= n; ++ i){ 37 read(a[i]); 38 _left[i] = _right[i] = i; 39 sum[i] = sum[i - 1] + a[i]; 40 while(l < r && a[i] <= a[q[r - 1]]) _left[i] = _left[q[r-1]],r--; 41 q[r++] = i; 42 } 43 44 l = r = 0; 45 46 for(int i = n;i >= 1; -- i){ 47 while(l < r && a[i] <= a[q[r - 1]]) _right[i] = _right[q[r-1]],r--; 48 q[r++] = i; 49 } 50 51 for(int i = 1;i <= n; ++ i) 52 ans = max(ans,(sum[_right[i]] - sum[_left[i]-1]) * a[i]); 53 printf("%lld",ans); 54 } 55 56 int main(){ 57 // file(); 58 readdata(); 59 work(); 60 return 0; 61 }