【单调队列】广告印刷

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 const int MAXN=400000;
 8 int llen[MAXN],rlen[MAXN],q[MAXN];
 9 __int64 h[MAXN];
10 int n;
11 
12 void input()
13 {
14     
15     scanf("%d",&n);
16     for (int i=0;i<n;i++) scanf("%lld",&h[i]);
17 }
18 
19 void CountLeft()
20 {
21     q[0]=-1;
22     int rear=1;
23     for (int i=0;i<n;i++) 
24     {
25         while (rear>1 && h[q[rear-1]]>=h[i]) rear--;
26         llen[i]=i-q[rear-1]-1;
27         q[rear]=i;
28         rear++;
29     }
30 }
31 
32 void CountRight()
33 {
34     q[0]=n;
35     int rear=1;
36     for (int i=n-1;i>=0;i--) 
37     {
38         while (rear>1 && h[q[rear-1]]>=h[i]) rear--;
39         rlen[i]=q[rear-1]-i-1;
40         q[rear]=i;
41         rear++;
42     }
43 }
44 
45 void output()
46 {
47     __int64 ans=0;
48     for (int i=0;i<n;i++)
49         ans=max(ans,(llen[i]+rlen[i]+1)*h[i]);
50     cout<<ans<<endl;
51 }
52 
53 int main()
54 {
55     freopen("mr452.in4","r",stdin);
56     freopen("mr452.ou4","w",stdout);
57     input();
58     CountLeft();
59     CountRight();
60     output();
61     return 0;
62 }