题解：P14311 【MX-S8-T4】平衡三元组

· · 题解

怎么没人打块啊。

赛时由于以为 lower_bound 是小于等于，调了 +\infty 个小时，整场都没调出来。

我们将 B_y-B_x\le B_z-B_y 转换一下，可以得到：3B_y\le B_x+B_y+B_z。

要求 B_x+B_y+B_z 的最大值，若 B_y 固定，分别求 B 数组的前缀最大与后缀最大，然后看看符不符合 3B_y\le B_x+B_y+B_z 的限制即可。到这一步你就直接上块了。

我们将原序列分成 \frac{n}{B} 个块，每个块的块长为 B，不光要对每个块进行排序，还要对每个块内的 2a_i-pre_{i-1}（贡献为 a_i+pre_{i-1}），2a_i-suf_{i+1}（贡献为 a_i+pre_{i+1}）（设 pre 数组表示的是这个块内的前缀最大，suf 数组表示的是这个块内的后缀最大）进行排序，还有每个块内的答案。

区间加就直接整块打标记，散块暴力改。

对于查询，散块直接暴力前缀后缀查，整块需要搞出来的比较多左右端点在块内或块外的答案。但似乎左端点在块内右端点在块外或相反的情况不太好搞。我们以左端点在块内右端点在块外为例。由 B_y-B_x\le B_z-B_y，可得 2B_y-B_x\le B_z。由于右端点已知，直接对于所有的 2B_y-B_x\le B_z，求出 B_x+B_y 的最大值，也就是我们如上每个块维护的顺序。对于相反的情况同理。

细节可能比较多，慢慢调就好了。时间复杂度为 O(q\sqrt{n\log n})。

然后就是喜闻乐见的卡常环节：

最后也是喜提最优解倒数第一页。

代码是良心真短，不算快读只有 5KB。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll 
using namespace std;
//此处省略快读
unsigned bucket[256];
#define SORTBYTE(TYPE, FR, TO, LEN, BIT) {\
    memset(bucket, 0, sizeof(bucket));\
    for (TYPE *it = (FR) + LEN; it != (FR); it--)\
        ++bucket[(it[-1] >> BIT) & 255];\
    for (unsigned *it = bucket; it != bucket + 255; it++)\
        it[1] += it[0];\
    for (TYPE *it = (FR) + LEN; it != (FR); it--)\
        (TO)[--bucket[(it[-1] >> BIT) & 255]] = it[-1];\
}
#define pll pair<long long,long long>
#define PSORTBYTE(TYPE, FR, TO, LEN, BIT) {\
    memset(bucket, 0, sizeof(bucket));\
    for (TYPE *it = (FR) + LEN; it != (FR); it--)\
        ++bucket[(it[-1].first >> BIT) & 255];\
    for (unsigned *it = bucket; it != bucket + 255; it++)\
        it[1] += it[0];\
    for (TYPE *it = (FR) + LEN; it != (FR); it--)\
        (TO)[--bucket[(it[-1].first >> BIT) & 255]] = it[-1];\
}
constexpr int N=1e6+5;
constexpr int B=4e3+5,block=1050;
long long a[N],b[N],pre2[N],suf2[N],pre[N],suf[N];
long long sum,st,k,ans[B];
pll c[N],d[N],c2[N],d2[N];
int n,q,bl[N],L[B],R[B],add[B];
inline void push_down(int x){
    for(int i=L[x];i<=R[x];++i)b[i]=(a[i]+=add[x])+2000000000;add[x]=0;
    SORTBYTE(long long,b+L[x],pre2+L[x],R[x]-L[x]+1,0);
    SORTBYTE(long long,pre2+L[x],b+L[x],R[x]-L[x]+1,8);
    SORTBYTE(long long,b+L[x],pre2+L[x],R[x]-L[x]+1,16);
    SORTBYTE(long long,pre2+L[x],b+L[x],R[x]-L[x]+1,24);
    for(int i=L[x];i<=R[x];++i)b[i]-=2000000000;
    pre[L[x]]=a[L[x]];for(int i=L[x]+1;i<=R[x];++i)pre[i]=max(pre[i-1],a[i]);
    suf[R[x]]=a[R[x]];for(int i=R[x]-1;i>=L[x];--i)suf[i]=max(suf[i+1],a[i]);
    ans[x]=-inf;
    for(int i=L[x]+1;i<R[x];++i)
    if((a[i]<<1)<=pre[i-1]+suf[i+1])ans[x]=max(ans[x],a[i]+pre[i-1]+suf[i+1]); 
    for(int i=L[x];i<R[x];++i)
    c2[i]=make_pair((a[i+1]<<1)-pre[i]+6000000000ll,a[i+1]+pre[i]),d2[i]=make_pair((a[i]<<1)-suf[i+1]+6000000000ll,a[i]+suf[i+1]);
    PSORTBYTE(pll,c2+L[x],c+L[x],R[x]-L[x],0);
    PSORTBYTE(pll,c+L[x],c2+L[x],R[x]-L[x],8);
    PSORTBYTE(pll,c2+L[x],c+L[x],R[x]-L[x],16);
    PSORTBYTE(pll,c+L[x],c2+L[x],R[x]-L[x],24);
    PSORTBYTE(pll,c2+L[x],c+L[x],R[x]-L[x],32);
    PSORTBYTE(pll,d2+L[x],d+L[x],R[x]-L[x],0);
    PSORTBYTE(pll,d+L[x],d2+L[x],R[x]-L[x],8);
    PSORTBYTE(pll,d2+L[x],d+L[x],R[x]-L[x],16);
    PSORTBYTE(pll,d+L[x],d2+L[x],R[x]-L[x],24);
    PSORTBYTE(pll,d2+L[x],d+L[x],R[x]-L[x],32);
    c[L[x]].first-=6000000000ll,d[L[x]].first-=6000000000ll;
    for(int i=L[x]+1;i<R[x];++i)c[i].first-=6000000000ll,d[i].first-=6000000000ll,
    c[i].second=max(c[i].second,c[i-1].second),d[i].second=max(d[i].second,d[i-1].second);
}
inline void query(int l,int r){
    sum=-inf;
    if(bl[l]==bl[r]){
        pre2[l]=a[l]+add[bl[l]];
        suf2[r]=a[r]+add[bl[l]];for(int i=r-1;i>l;--i)suf2[i]=max(suf2[i+1],a[i]+add[bl[l]]);
        for(int i=l+1;i<r;++i){
            pre2[i]=max(pre2[i-1],a[i]+add[bl[l]]);
            if(((a[i]+add[bl[l]])<<1)<=pre2[i-1]+suf2[i+1])
            sum=max(sum,a[i]+add[bl[l]]+pre2[i-1]+suf2[i+1]);
        }
        (sum==-inf)?(cout<<"No\n"):(cout<<sum<<'\n');
        return;
    }
    pre2[l]=a[l]+add[bl[l]];for(int i=l+1;i<=R[bl[l]];++i)pre2[i]=max(pre2[i-1],a[i]+add[bl[l]]);
    suf2[r]=a[r]+add[bl[r]];for(int i=r-1;i>=L[bl[r]];--i)suf2[i]=max(suf2[i+1],a[i]+add[bl[r]]);

    for(int i=bl[l]+1;i<bl[r];++i)pre2[R[i]]=max(pre[R[i]]+add[i],pre2[R[i-1]]);
    for(int i=bl[r]-1;i>bl[l];--i)suf2[L[i]]=max(suf[L[i]]+add[i],suf2[L[i+1]]);

    for(int i=R[bl[l]];i>=l;--i)suf2[i]=max(suf2[i+1],a[i]+add[bl[l]]);
    for(int i=L[bl[r]];i<=r;++i)pre2[i]=max(pre2[i-1],a[i]+add[bl[r]]);
    for(int i=R[bl[l]];i>l;--i)if(a[i]+add[bl[l]]+a[i]+add[bl[l]]<=pre2[i-1]+suf2[i+1])
    sum=max(sum,a[i]+add[bl[l]]+pre2[i-1]+suf2[i+1]);

    for(int i=L[bl[r]];i<r;++i)if(a[i]+add[bl[r]]+a[i]+add[bl[r]]<=pre2[i-1]+suf2[i+1])
    sum=max(sum,a[i]+add[bl[r]]+pre2[i-1]+suf2[i+1]);
    for(int i=bl[l]+1;i<bl[r];++i){
        if(ans[i]!=-inf)sum=max(sum,ans[i]+add[i]+add[i]+add[i]);
        st=pre2[R[i-1]]+suf2[L[i+1]];
        if(b[L[i]]<=((st)>>1)-add[i]){
            sum=max(sum,(*(upper_bound(b+L[i],b+R[i]+1,((st)>>1)-add[i])-1))+add[i]+st);
        }
        if(c[L[i]].first<=suf2[L[i+1]]-add[i]){
            sum=max(sum,(*(upper_bound(c+L[i],c+R[i],make_pair(suf2[L[i+1]]-add[i],inf))-1)).second+add[i]+add[i]+suf2[L[i+1]]);
        }
        if(d[L[i]].first<=pre2[R[i-1]]-add[i]){
            sum=max(sum,(*(upper_bound(d+L[i],d+R[i],make_pair(pre2[R[i-1]]-add[i],inf))-1)).second+add[i]+add[i]+pre2[R[i-1]]);
        }
    }
    (sum==-inf)?(cout<<"No\n"):(cout<<sum<<'\n');
    return;
}
inline void update(int l,int r,long long x){
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;++i)a[i]+=x;
        push_down(bl[l]);
        return;
    }
    for(int i=R[bl[l]];i>=l;--i)a[i]+=x;
    for(int i=L[bl[r]];i<=r;++i)a[i]+=x; 
    push_down(bl[l]);push_down(bl[r]);
    for(int i=bl[l]+1;i<bl[r];++i)add[i]+=x;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=block;++i)bl[i]=1;
    for(int i=block+1;i<=n;++i)bl[i]=bl[i-block]+1;
    for(int i=1;i<=bl[n];++i)L[i]=(i-1)*block+1,R[i]=min(i*block,n),push_down(i);
    int op,l,r;long long x;
    for(int i=1;i<=q;++i)cin>>op>>l>>r,(op==1)?(query(l,r)):(cin>>x,update(l,r,x));
    return 0;
}