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

· · 题解

Solution

不妨思考一下若给定一个 B，如何快速求出 f(B)。

接下来不妨认为 z 取到了全局最大值，x 取到的情况是类似的。将前缀最大值的位置抠出来，设其依次为 p_1,p_2,\cdots,p_m。

证明：设 y=p_k，x=p_{k-1}。若 (x,y,z) 不合法，则有 B_{p_k}-B_{p_{k-1}}>B_{p_m}-B_{p_k}，那么有 B_{p_m}-B_{p_{k-1}}>2(B_{p_m}-B_{p_k})。由于 0\le B_{p_m}-B_{p_i}\le B_{p_m}，至多 O(\log V) 轮后会找到第一个合法的 p_k，而往下继续找由于答案更小，是没有意义的。

在 B_y 是前缀最大值的部分迭代 O(\log V) 轮时顺便统计这部分的贡献即可，找到一个合法的是前缀最大值的 B_y 后继续往下找仍然是没有意义的。

那么线段树维护区间加、求区间 \max 及其位置即可做到 O(n+q\log n\log V)，可以通过。

Code

bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=1e6+5,mod=998244353,INF=1e9;
constexpr ll LINF=1e18;
inline ll add(ll x,ll y){return (x+=y)>=mod&&(x-=mod),x;}
inline ll Add(ll &x,ll y){return x=add(x,y);}
inline ll sub(ll x,ll y){return (x-=y)<0&&(x+=mod),x;}
inline ll Sub(ll &x,ll y){return x=sub(x,y);}
inline ll qpow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}
int n,q,a[N];
struct node{
    int val,pos;
    node(){val=pos=0;}
    node(int _val,int _pos){val=_val,pos=_pos;}
};
inline bool operator <(const node &a,const node &b){
    return a.val<b.val;
}
int L[N<<2],R[N<<2],M[N<<2],Tag[N<<2];node Max[N<<2];
inline void pushup(int p){Max[p]=max(Max[p<<1],Max[p<<1|1]);}
inline void pushTag(int p,int v){Max[p].val+=v,Tag[p]+=v;}
inline void pushdown(int p){if(Tag[p])pushTag(p<<1,Tag[p]),pushTag(p<<1|1,Tag[p]),Tag[p]=0;}
void build(int l,int r,int p=1){
    L[p]=l,R[p]=r,M[p]=(l+r)>>1,Tag[p]=0;
    if(l==r){
        Max[p]=node(a[l],l);
        return;
    }
    build(L[p],M[p],p<<1);
    build(M[p]+1,R[p],p<<1|1);
    pushup(p);
}
inline void mdf(int l,int r,int v,int p=1){
    if(l<=L[p]&&R[p]<=r){
        pushTag(p,v);
        return;
    }
    pushdown(p);
    if(l<=M[p])mdf(l,r,v,p<<1);
    if(M[p]<r)mdf(l,r,v,p<<1|1);
    pushup(p);
}
inline node qry(int l,int r,int p=1){
    if(l<=L[p]&&R[p]<=r)return Max[p];
    pushdown(p);
    if(r<=M[p])return qry(l,r,p<<1);
    if(M[p]<l)return qry(l,r,p<<1|1);
    return max(qry(l,r,p<<1),qry(l,r,p<<1|1));
}
bool Med;
int main(){
    cerr<<abs(&Mst-&Med)/1048576.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            ll ans=-LINF;node all=qry(l,r);
            int val=all.val,pos=all.pos;
            if(l<pos){
                node cur=qry(l,pos-1),nxt;
                for(int maxy=cur.pos+1<pos?qry(cur.pos+1,pos-1).val:-INF;cur.pos>=l;cur=nxt){
                    int cval=cur.val,cpos=cur.pos;
                    if(maxy>-INF)
                        ans=max(ans,(ll)cval+maxy+val);
                    if(l<cpos){
                        nxt=qry(l,cpos-1);
                        int nval=nxt.val,npos=nxt.pos;
                        if(cval<=((nval+val)>>1)){
                            ans=max(ans,(ll)nval+cval+val);
                            break;
                        }
                        else if(npos+1<cpos)
                            maxy=max(maxy,qry(npos+1,cpos-1).val);
                    }
                    else break;
                }
            }
            if(pos<r){
                node cur=qry(pos+1,r),nxt;
                for(int maxy=pos<cur.pos-1?qry(pos+1,cur.pos-1).val:-INF;cur.pos<=r;cur=nxt){
                    int cval=cur.val,cpos=cur.pos;
                    if(maxy>-INF)
                        ans=max(ans,(ll)val+maxy+cval);
                    if(cpos<r){
                        nxt=qry(cpos+1,r);
                        int nval=nxt.val,npos=nxt.pos;
                        if(cval<=((val+nval)>>1)){
                            ans=max(ans,(ll)val+cval+nval);
                            break;
                        }
                        else if(cpos+1<npos)
                            maxy=max(maxy,qry(cpos+1,npos-1).val);
                    }
                    else break;
                }
            }
            if(ans>-LINF)cout<<ans<<'\n';
            else cout<<"No\n";
        }
        else{
            int l,r,x;cin>>l>>r>>x;
            mdf(l,r,x);
        }
    }
    return 0;
}