A. 柱状图
B. 应急棍
C. 擒敌拳
考场上测试点分治切了,单调队列 \(+\) 斜率优化.
每次枚举队列里的所有元素就行了.
正解是李超线段树.
C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long int
#define ull unsigned ll
#define lf double
#define lbt(x) (x&(-x))
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read() {
int ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=2e5+21;
namespace DEQUE{
struct Deque{
ll l,r; ll q[N<<2];
inline bool empty(){ return l>r; }
inline ll size(){ return r-l+1; }
inline ll front(){ return q[l]; }
inline ll back(){ return q[r]; }
inline void pop_front(){ l++; }
inline void pop_back(){ r--; }
inline void push_front(ll x){ q[--l]=x; }
inline void push_back(ll x){ q[++r]=x; }
} que;
} using namespace DEQUE;
ll m,n,maxh,ans,flag;
ll H[N];
struct I { ll h,id,lc; } p[N];
inline void Work1(){
ll now;
for(int i=1;i<=n;i++){
maxh=max(maxh,p[i].h),p[i].lc=i;
if(que.empty()) que.push_back(i),ans=max(ans,p[i].h);
else{
if(p[que.back()].h<p[i].h) que.push_back(i);
else{
while(que.size() and p[que.back()].h>=p[i].h){
now=que.back(),que.pop_back();
p[i].lc=min(p[now].lc,p[i].lc);
}
que.push_back(i);
}
for(int j=que.l;j<=que.r;j++){
ans=max(ans,(i-p[que.q[j]].lc+1)*p[que.q[j]].h);
}
}
printf("%lld ",max(ans,maxh));
}
}
inline ll caly(ll x){ return x*H[x]-H[x]; }
inline lf getxl(ll a,ll b){ return 1.0*(caly(a)-caly(b))/(H[a]-H[b]); }
inline void Work2(){
for(int i=1;i<=n;i++) H[i]=p[i].h;
que.push_back(1); ll res=0; printf("%lld ",H[1]);
for(int i=2;i<=n;i++){
while(que.l<que.r and getxl(que.q[que.l+1],que.front())<=i) que.pop_front();
res=max(H[i],H[que.front()]*i-caly(que.front()));
while(que.l<que.r and getxl(i,que.back())<=getxl(que.back(),que.q[que.r-1])) que.pop_back();
que.push_back(i);
printf("%lld ",res);
}
}
signed main(){
FILE(b);
n=read(),que.l=n+1,que.r=n;flag=1;
for(int i=1;i<=n;i++) p[i].h=read(),flag&=(p[i].h>=p[i-1].h);
if(flag) Work2();
else Work1();
exit(0);
}