2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4 [2021/04/26 17:08] jxm2001 [题解] |
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training4 [2021/04/30 18:55] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 304: | 行 304: | ||
| enter(ss[ans[i]]); | enter(ss[ans[i]]); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== L. Two Buildings ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个长度为 $n$ 的序列 $h$，询问 $\max((h_l+h_r)(r-l))$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑枚举右端点，维护左端点信息。不难发现，需要考虑的左端点一定满足单调递增，因为最优解一定不属于非递增的点。 | ||
| + | |||
| + | 同时，需要考虑的右端点一定单调递减，因为最优解一定不属于非递减的点。 | ||
| + | |||
| + | 通过推式子可以发现对应右端点对于左端点的决策满足单增性，于是考虑单调队列二分或分治 $O(n\log n)$ 处理。 | ||
| + | |||
| + | <hidden 单调队列二分版本> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e6+5; | ||
| + | int h[MAXN],a[MAXN],b[MAXN]; | ||
| + | struct Seg{ | ||
| + | int lef,rig,idx; | ||
| + | Seg(int lef=0,int rig=0,int idx=0):lef(lef),rig(rig),idx(idx){} | ||
| + | }que[MAXN]; | ||
| + | LL cal(int l,int r){ | ||
| + | return 1LL*(h[a[r]]+h[l])*(a[r]-l); | ||
| + | } | ||
| + | int cutSeg(int lef,int rig,int idx1,int idx2){ | ||
| + | int ans; | ||
| + | while(lef<=rig){ | ||
| + | int mid=lef+rig>>1; | ||
| + | if(cal(idx1,mid)>cal(idx2,mid)){ | ||
| + | ans=mid; | ||
| + | lef=mid+1; | ||
| + | } | ||
| + | else | ||
| + | rig=mid-1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),qcnt=0,mcnt=0; | ||
| + | _rep(i,1,n)h[i]=read_int(); | ||
| + | _rep(i,1,n){ | ||
| + | while(qcnt&&h[a[qcnt]]<=h[i])qcnt--; | ||
| + | a[++qcnt]=i; | ||
| + | if(mcnt==0||h[b[mcnt]]<h[i]) | ||
| + | b[++mcnt]=i; | ||
| + | } | ||
| + | int mpos=1,head=1,tail=0; | ||
| + | que[++tail]=Seg(1,qcnt,b[mpos++]); | ||
| + | LL ans=0; | ||
| + | _rep(i,1,qcnt){ | ||
| + | while(head<=tail&&que[head].rig<i)head++; | ||
| + | que[head].lef=i; | ||
| + | while(mpos<=mcnt&&b[mpos]<a[i]){ | ||
| + | if(cal(b[mpos],qcnt)>cal(que[tail].idx,qcnt)){ | ||
| + | while(head<=tail&&cal(que[tail].idx,que[tail].lef)<=cal(b[mpos],que[tail].lef))tail--; | ||
| + | if(head<=tail){ | ||
| + | int p=cutSeg(que[tail].lef,que[tail].rig,que[tail].idx,b[mpos]); | ||
| + | que[tail].rig=p; | ||
| + | que[++tail]=Seg(p+1,qcnt,b[mpos]); | ||
| + | } | ||
| + | else | ||
| + | que[++tail]=Seg(i,qcnt,b[mpos]); | ||
| + | } | ||
| + | mpos++; | ||
| + | } | ||
| + | ans=max(ans,cal(que[head].idx,i)); | ||
| + | } | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | <hidden 分治版本> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e6+5; | ||
| + | int h[MAXN],a[MAXN],b[MAXN]; | ||
| + | LL cal(int l,int r){ | ||
| + | return 1LL*(h[a[r]]+h[b[l]])*(a[r]-b[l]); | ||
| + | } | ||
| + | LL solve(int ql,int qr,int sl,int sr){ | ||
| + | if(ql>qr)return 0; | ||
| + | LL ans=-1; | ||
| + | int qmid=ql+qr>>1,smid; | ||
| + | _rep(i,sl,sr){ | ||
| + | if(ans<cal(i,qmid)){ | ||
| + | ans=cal(i,qmid); | ||
| + | smid=i; | ||
| + | } | ||
| + | } | ||
| + | return max(ans,max(solve(ql,qmid-1,sl,smid),solve(qmid+1,qr,smid,sr))); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),qcnt=0,mcnt=0; | ||
| + | _rep(i,1,n)h[i]=read_int(); | ||
| + | _rep(i,1,n){ | ||
| + | while(qcnt&&h[a[qcnt]]<=h[i])qcnt--; | ||
| + | a[++qcnt]=i; | ||
| + | if(mcnt==0||h[b[mcnt]]<h[i]) | ||
| + | b[++mcnt]=i; | ||
| + | } | ||
| + | enter(solve(1,qcnt,1,mcnt)); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/2021_buaa_spring_training4.1619428091.txt.gz · 最后更改: 2021/04/26 17:08 由 jxm2001
