一种更优秀的「EZEC-5」魔法 做法

可以证明，所有的 $1,2$ 操作都会对整个区间进行，并且先做 $1$ 操作后做 $2$ 操作。末处补充证明~~性感理解~~。 考虑 2 操作对 $s$ 的影响，则 $2^ksum\ge s$ 意味着 $sum\ge \frac{s}{2^k}$，这时我们发现 2 操作可以不视为对序列操作而是视为对 $s$ 操作。 2 操作次数显然是可以枚举的，所以题目转化为求最小 1 操作次数。 对于同一长度，同样操作次数加的值是一样的，也就是说同一长度只要保留最大子段和就可以了。 那么可以考虑计算所有不同长度的子段的最大子段和。由于修改只有整体加，那么类似斜率优化可以知道有用的 $(len,s_{len})$ 构成一个凸包。那么可以发现 这玩意不就是[世上最幸福的女孩](https://www.luogu.com.cn/problem/P5073)？？ 所以跑个闵科夫斯基和合并凸包，再枚举 2 操作次数即可。 总时间复杂度 $O(n\log n+nloga)$，空间复杂度 $O(n\log n)$，明显会 MLE 那题写线性空间挺烦的，我们可以考虑最终只需要全局最大子段和，不需要保存每一层的凸包，那么滚动数组就好了。 另外根据斜率优化的原理应该可以轻易做到 $O(n\log n+\log a)$，这里不展开。 以下是证明部分 先证明先做 1 后做 2 因为 2 操作是乘法，那么考虑 1 对 2 的贡献可证明。 1 操作对整个区间做十分显然，不叙 关于 2 操作，首先考虑到所有子段进行完 1 操作后与长度没有关系，可以直接选出同样 1 操作次数的最大子段和，由于选取的是最大子段和 $[l,r]$，那么不存在 $i\in [l,r]$ 使得 $\max([l,i],[i,r])>[l,r]$，则若 2 操作对 $[ll,rr]$ 做更优，则观察增量 $[ll,rr]\times 2>[l,r]*2$，分别令 $i=ll,i=rr$ 可推出与上式矛盾。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+2,M=4e5+2,K=2; const ll inf=-9e18; struct pt { int x; ll y; pt(int a=0,ll b=inf):x(a),y(b){} bool operator<(register pt o) {return ((ll)x*o.y<(ll)y*o.x)||((ll)x*o.y==(ll)y*o.x)&&(x+y<o.x+o.y);}//顺时针 pt operator+(register pt &o) {return pt(x+o.x,y+o.y);} pt operator-(register pt &o) {return pt(x-o.x,y-o.y);} ll operator*(register pt o) {return (ll)x*o.y-(ll)y*o.x;} void operator+=(register pt &o) {x+=o.x;y+=o.y;} void operator-=(register pt &o) {x-=o.x;y-=o.y;} }; pt sl[K][N],sr[K][N],ss[K][N]; pt st[N],la[N],lb[N]; ll sa[N]; int l[M],a[N],r[M],cs[M],lcd[M],rcd[M],scd[M]; int n,i,j,x,y,z; inline void mx(register ll &x,const ll y) { if (x<y) x=y; } inline void read(int &x) { int c=getchar(),fh=1; while (c<48||c>57) { if (c=='-') {c=getchar();fh=-1;break;} c=getchar(); } x=c^48;c=getchar(); while ((c>=48)&&(c<=57)) { x=x*10+(c^48); c=getchar(); } x*=fh; } void tb(register pt *a,int pre,register int &n) { register int i,tp=pre; for (i=tp+1;i<=n;i++) { while (tp) { if (a[tp].y<=a[i].y) --tp; else if ((tp>1)&&(a[i]-a[tp-1]<a[tp]-a[tp-1])) --tp; else break; } a[++tp]=a[i]; } n=tp; } void maintain(register pt *a,const int n,const int m) { register int i; for (i=m;i>n;i--) a[a[i].x=i].y=inf; for (i=n;i;i--) {a[a[i].x]=a[i];a[a[i].x=i].y=inf;} } void spemaintain(register pt *a,const int n,const int m) { register int tp=0,i; for (i=1;i<=m;i++) st[st[i].x=i].y=inf; for (i=1;i<=n;i++) mx(st[a[i].x].y,a[i].y); memcpy(a+1,st+1,m*sizeof(pt)); } int order(register pt *a,register int n) { register int i=1,tp=0; for (i=1;i<=n;i++) if (a[i].y>inf) a[++tp]=a[i]; tb(a,1,tp);return tp; } int sum(pt *a,pt *b,pt *c,int n,int m,int len)//a+b=c { int i,j,tp=2; c[1]=a[1]+b[1]; for (i=1;i<n;i++) la[i]=a[i+1]-a[i];la[n]=a[1]-a[n]; for (i=1;i<m;i++) lb[i]=b[i+1]-b[i];lb[m]=b[1]-b[m]; for (i=j=1;(i<=n)||(j<=m);++tp) {if ((j>m)||(i<=n)&&(la[i]<lb[j])) c[tp]=c[tp-1]+la[i++]; else c[tp]=c[tp-1]+lb[j++];} --tp;spemaintain(c,tp,len);tp=order(c,len);tb(c,1,tp);return tp; } void build(int x) { if (l[x]==r[x]) { lcd[x]=rcd[x]=scd[x]=1;sl[cs[x]][l[x]]=sr[cs[x]][l[x]]=ss[cs[x]][l[x]]=pt(1,a[l[x]]); return; } register int c,cd; register ll ys; l[c=x<<1]=l[x];r[c]=l[x]+r[x]>>1; l[c|1]=r[c]+1;r[c|1]=r[x]; cs[c]=cs[c|1]=cs[x]^1; build(c);build(x<<1|1);c=x<<1; memset(ss[cs[x]]+l[x],0,(r[x]-l[x]+1)*sizeof(pt)); memset(sl[cs[x]]+l[x],0,(r[x]-l[x]+1)*sizeof(pt)); memset(sr[cs[x]]+l[x],0,(r[x]-l[x]+1)*sizeof(pt)); scd[x]=sum(sr[cs[c]]+l[c]-1,sl[cs[c]]+l[c|1]-1,ss[cs[x]]+l[x]-1,rcd[c],lcd[c|1],r[x]-l[x]+1); maintain(ss[cs[x]]+l[x]-1,scd[x],r[x]-l[x]+1); for (register int i=0;i<scd[c];i++) mx(ss[cs[x]][l[x]+ss[cs[c]][l[c]+i].x-1].y,ss[cs[c]][l[c]+i].y); memcpy(sl[cs[x]]+l[x],sl[cs[c]]+l[c],lcd[c]*sizeof(pt));lcd[x]=lcd[c];cd=r[c]-l[c]+1;ys=sa[r[c]]-sa[l[c]-1];c|=1; for (register int i=0;i<lcd[c];i++) sl[cs[x]][l[x]+(lcd[x]++)]=pt(sl[cs[c]][l[c]+i].x+cd,ys+sl[cs[c]][l[c]+i].y); tb(sl[cs[x]]+l[x]-1,lcd[c^1],lcd[x]); for (register int i=0;i<scd[c];i++) mx(ss[cs[x]][l[x]+ss[cs[c]][l[c]+i].x-1].y,ss[cs[c]][l[c]+i].y); scd[x]=order(ss[cs[x]]+l[x]-1,r[x]-l[x]+1); memcpy(sr[cs[x]]+l[x],sr[cs[c]]+l[c],rcd[c]*sizeof(pt));rcd[x]=rcd[c];cd=r[c]-l[c]+1;ys=sa[r[c]]-sa[l[c]-1];c^=1; for (register int i=0;i<rcd[c];i++) sr[cs[x]][l[x]+(rcd[x]++)]=pt(sr[cs[c]][l[c]+i].x+cd,ys+sr[cs[c]][l[c]+i].y); tb(sr[cs[x]]+l[x]-1,rcd[c^1],rcd[x]); } int main() { ll ans=9e18; int aa,bb,sss; read(n);read(aa);read(bb);read(sss); for (i=1;i<=n;i++) read(a[i]),sa[i]=sa[i-1]+a[i]; r[l[1]=1]=n;build(1); for (i=1;i<=scd[1];i++) { x=ss[cs[1]][i].x; ll y=ss[cs[1]][i].y;int s=sss; for (j=0;s>y&&s>1;j++) { ans=min(ans,(ll)bb*j+(ll)aa*((s-y-1)/x+1)); s=s+1>>1; } if (s>y) ans=min(ans,(ll)bb*j+(ll)aa*((s-y-1)/x+1)); else ans=min(ans,(ll)bb*j); } printf("%lld",ans); } ```