P2659 美丽的序列

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

P2659 美丽的序列
对于当前的最小值，找到最大的左右边界，然后更新答案。用单调队列确定左右边界，O（n）做法。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<map>

 #include<stack>

 #include<cstring>

 #define inf 2147483647

 #define For(i,a,b) for(register long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.11.2

 using namespace std;

 long long ans;

 long long n;

 struct node

 {

     long long l,r;

 }aa[];

 long long q[];

 long long l,r;

 long long x;

 long long a[];

 void in(long long &x)

 {

     long long y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=(x<<)+(x<<)+c-'',c=g();

     x*=y;

 }

 void o(long long x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 int main()

 {

     in(n);

     l=,r=;

     For(i,,n)

     in(a[i]);

     For(i,,n)

     {

         while(l<=r&&a[q[r]]>=a[i])aa[q[r--]].r=i-;

         aa[i].l=q[r++]+;

         q[r]=i;

     }

     while(l<=r)aa[q[r--]].r=n;

     For(i,,n)

     ans=max(ans,(aa[i].r-aa[i].l+)*a[i]);

     o(ans);

      return ;

 }