题解：P12241 [蓝桥杯 2023 国 C] 最大区间
怎么全是单调栈题解？那我写一篇 ST 表二分的吧。
枚举
code:
//Do not hack it
// @author fkxr(luogu uid=995934)
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#define ds(x) (x=='\r'||x=='\n'||x==' ')
#define MAX 20
namespace fastIO {
template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
struct Srr {
inline Srr operator>>(int& a) { r(a); return{}; }
inline Srr operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; }
inline Srr operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; }
template<typename T>inline Srr operator<<(T& a) { r(a); return{}; }
inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } }
}in;
struct Sww {
inline Sww operator<<(const int a) { w(a); return{}; }
inline Sww operator<<(const char ch) { pc(ch); return{}; }
inline Sww operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
template<typename T>inline Sww operator>>(const T a) { w(a); return{}; }
}out;
}using fastIO::in; using fastIO::out;
#undef ds
#define eout cerr
namespace Maths {
const bool __is_P[] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1 };
inline bool IP1(const int a) { if (a <= 29)return __is_P[a]; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0)return 0; for (int i = 6;; i += 6) { if (((i + 1) * (i + 1)) > a)return 1; if (a % (i + 1) == 0)return 0; if (((i + 5) * (i + 5)) > a)return 1; if (a % (i + 5) == 0)return 0; } }
#define times(a,b,m) (c=(unsigned long long)a*b-(unsigned long long)((long double)a/m*b+0.5L)*m,c<m?c:m+c)
inline int power(int a, int b, const int mod = -1) { unsigned long long c; int ans = 1; if (mod == -1) { for (; b;) { if (b & 1)ans *= a; b >>= 1; a *= a; }return ans; }for (; b;) { if (b & 1)ans = times(ans, a, mod); b >>= 1; a = times(a, a, mod); }return ans; }
const int Suk[] = { 2,325,9375,28178,450775,9780504,1795265022 };
inline bool chk(const int n, int a, int b, int x) { if (x >= n) return 1; unsigned long long c; int v = power(x, a, n); if (v == 1)return 1; int j = 1; while (j <= b) { if (v == n - 1)break; v = times(v, v, n); j++; }if (j > b)return 0; return 1; }
inline bool IP(int n) { if (n < 3 || n % 2 == 0)return n == 2; if (n <= 1e6) { return IP1(n); } else { int a = n - 1, b = 0; while (a % 2 == 0)a >>= 1, b++; for (int k : Suk)if (!chk(n, a, b, k))return 0; return 1; } }
#undef times
} using Maths::power;
using Maths::IP;
namespace exs{
#define _4x _4x
#ifdef _4x
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
#else
int dx[]={1,0,-1,-1,1,1,0,-1},dy[]={1,1,1,0,0,-1,-1,-1};
#endif
template<typename T,typename T1,typename T2>inline bool rg(T l,T1 r,T2 x){return l<=x&&x<=r;}
inline bool emc(const int&a,const int&b){return a>b;}
}using namespace exs;
//#define BIT BIT
#ifdef BIT
namespace BIT {//下标从1开始
#define maxn 100005
struct ds {//打死要记住初始化 ds.n
int c0[maxn], c1[maxn], n;
inline void Add(int* c, int p, int v) { for (; p <= n; p += p & -p)c[p] += v; }
inline int Sum(int* c, int p) { int t = 0; for (; p; p -= p & -p)t += c[p]; return t; }
inline int sum(int l, int r) { return Sum(c0, r) * r - Sum(c1, r) - Sum(c0, l - 1) * (l - 1) + Sum(c1, l - 1); }
inline void add(int l, int r, int v) { Add(c0, l, v); Add(c0, r + 1, -v); Add(c1, l, (l - 1) * v); Add(c1, r + 1, -r * v); }
inline void init(int* c, int len) { int last = 0; for (int i = 1; i <= len; i++) { last = c[i] - last; Add(c0, i, last); Add(c1, i, last * (i - 1)); last = c[i]; } }
};
#undef maxn
}using namespace BIT;
#endif
#define ST ST
#ifdef ST
namespace ST {//下标从1开始
struct st {
#define maxn 300005
#define bq min
int lg[maxn], f[20][maxn];
inline void init(int*c, int len) { for (int i = 2; i <= len; i++)lg[i] = lg[i >> 1] + 1; for (int i = 1; i <= len; i++)f[0][i] = c[i]; for (int j = 1; (1 << j) <= len; j++) { for (int i = 1; i + (1 << j) - 1 <= len; i++)f[j][i] = bq(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]); } }
inline int q(int l, int r) { int j = lg[r - l + 1]; return bq(f[j][l], f[j][r - (1 << j) + 1]); }
};
#undef maxn
#undef bq
}using namespace ST;
#endif
st t;
int a[300005];
signed main() {
int n;
in>>n;
a[1]=a[n+2]=0;
for(int i=2;i<=n+1;i++)
in>>a[i];
t.init(a,n+2);
int ans=0;
for(int i=2;i<=n+1;i++){
int L=i,l=1,r=i;
for(;l<=r;){
int mid=l+r>>1;
if(t.q(mid,i)!=a[i])
l=mid+1;
else
r=mid-1,L=mid;
}
int R=i;l=i,r=n+1;
for(;l<=r;){
int mid=l+r>>1;
if(t.q(i,mid)!=a[i])
r=mid-1;
else
l=mid+1,R=mid;
}
ans=max(ans,a[i]*(R-L+1));
}
out<<ans<<'\n';
return 0;
}提交记录
时间复杂度明显是