首页 > 代码库 > [luoguP2659] 美丽的序列(单调栈)
[luoguP2659] 美丽的序列(单调栈)
传送门
单调栈大水题
l[i] 表示 i 能扩展到的左边
r[i] 表示 i 能扩展到的右边
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define LL long long 4 5 const int MAXN = 2000002; 6 int n, t; 7 LL ans, a[MAXN], s[MAXN], l[MAXN], r[MAXN]; 8 9 inline int read()10 {11 int x = 0, f = 1;12 char ch = getchar();13 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;14 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;15 return x * f;16 }17 18 inline LL max(LL x, LL y)19 {20 return x > y ? x : y;21 }22 23 int main()24 {25 int i;26 n = read();27 for(i = 1; i <= n; i++) a[i] = read();28 a[0] = a[n + 1] = -1;29 for(i = 1; i <= n + 1; i++)30 {31 while(t && a[s[t]] > a[i]) r[s[t--]] = i;32 s[++t] = i;33 }34 t = 0;35 for(i = n; i >= 0; i--)36 {37 while(t && a[s[t]] > a[i]) l[s[t--]] = i;38 s[++t] = i;39 }40 for(i = 1; i <= n; i++) ans = max(ans, a[i] * (r[i] - l[i] - 1));41 printf("%lld\n", ans);42 return 0;43 }
[luoguP2659] 美丽的序列(单调栈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。