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

· · 题解

我们从暴力开始考虑，对于一个确定的区间 [l,r] 和 y ，A_x 和 A_z 一定会取到 [l,y) 和 (y,r] 的前/后缀最大值。

感性理解一下，y 确定时，A_x 和 A_z 越大，更容易满足 2 \times A_y \le A_x + A_z 的限制，同时会使价值更大，是一个双赢的局面。

处理一下区间前/后缀最大值，枚举 y ，即可做到 O(nq) 的暴力做法。

进一步思考，当答案最优时，A_x 或 A_z 一定会取到区间内的最大值(除非 y 不得不取到最大值)，所以我们就可以确定三元组的一个端点。

我们先考虑 A_x 取到最大值的情况，设 m_0=x ，我们求出 (pos,r] 的最大值的位置为 m_1 ，那么所有在 (m_0,m_1) 之间的 y 都是合法的，因为限制式子相当于让 A_y \le \frac{A_x+A_z}{2} ，现在 A_{m_0} 和 A_{m_1} 都大于等于 A_y ，所以他们的平均值也一定大于等于 A_y ， 所以我们直接取 (m_0,m_1) 中的 A 的最大值计算贡献即可。

接下来我们 y=m_1 的情况，x,y 已经确定，z 沿用暴力时的思路，取 (m_1,r] 中的最大值 m_2 作为 z 判断是否合法。

如果合法，该答案即为最优答案，因为 m_0,m_1,m_2 分别是可取区间内的最大值的位置，不会再有合法区间内的其他值使答案更优。

如果不合法，我们继续向后重复这个过程，选定 m_2 为 (m_1,r] 区间内的最大值的位置，对这个子问题递归求解即可，直到满足要求或区间长度不足选出两个数。

最后我们证明时间复杂度： 主要的复杂度分析在于递归的次数的数量级，我们考虑何时会进行下一层递归: $$ 2 \times A_{m_1} > A_{m_0}+A_{m_2} $$ 移项得 $$ A_{m_2} < 2 \times A_{m_1}-A_{m_0} $$ 子问题的递归条件同理为 $$ A_{m_3} < 2\times A_{m_2} -A_{m_0} =4 \times A_{m_1} -3\times A_{m_0} $$ 归纳总结可得递归条件为 $$ A_{m_n} <2^{n-1} (A_{m_1} - A_{m_0}) +A_{m_0} $$ 显然最多递归 $\log V$ 次，其中 $V$ 为值域。 我们在这个过程中只用到了求区间最大值及其位置，可以用线段树平凡的维护，修改操作的区间加是平凡的。 所以复杂度为 $O(q\log n \log V)

这道题的代码是比较好写的，是一道偏思维的 DS 题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[(int)2e6];
struct Seg{
    #define ls i<<1
    #define rs i<<1|1
    #define mid ((l+r)>>1)
    int mx[(int)5e6],pos[(int)5e6],laz[(int)5e6];
    void build(int i,int l,int r){
        if(l==r)return mx[i]=a[l],pos[i]=l,void();
        build(ls,l,mid),build(rs,mid+1,r),push_up(i);
    }
    void down(int i){
        if(!laz[i])return ;
        mx[ls]+=laz[i],mx[rs]+=laz[i];
        laz[ls]+=laz[i],laz[rs]+=laz[i];laz[i]=0;
    }
    void push_up(int i){
        mx[i]=max(mx[ls],mx[rs]);
        pos[i]=mx[i]==mx[ls]?pos[ls]:pos[rs];
    }
    void add(int i,int l,int r,int x,int y,int k){
        if(x<=l&&y>=r)return mx[i]+=k,laz[i]+=k,void();
        down(i);if(x<=mid)add(ls,l,mid,x,y,k);
        if(y>mid)add(rs,mid+1,r,x,y,k);push_up(i);
    }
    pair<int,int> query(int i,int l,int r,int x,int y){
        if(x<=l&&y>=r)return {mx[i],pos[i]};pair<int,int> ans={-1e9,0};
        down(i);if(y<=mid)return query(ls,l,mid,x,y);
        if(x>mid)return query(rs,mid+1,r,x,y);
        auto [val1,P1]=query(ls,l,mid,x,y);
        auto [val2,P2]=query(rs,mid+1,r,x,y);
        return {max(val1,val2),val1>=val2?P1:P2};
    }int operator [](const int &x){return this->query(1,1,n,x,x).first;}
    int operator [](const pair<int,int> x){return this->query(1,1,n,x.first,x.second).first;}
    #undef mid
}T;
int ans=0;
void solver(int l,int r,int Mx){
    // cout<<l<<' '<<r<<'\n';
    if(l>=r)return ;
    auto [mx,pos]=T.query(1,1,n,l,r);
    if(pos!=l)ans=max(ans,T[{l,pos-1}]+mx+Mx);
    if(pos==r)return ;
    if(2*mx<=Mx+T[{pos+1,r}])return ans=max(ans,mx+T[{pos+1,r}]+Mx),void();
    else solver(pos+1,r,Mx);
}
void solvel(int l,int r,int Mx){
    // cout<<l<<' '<<r<<'\n';
    if(l>=r)return ;
    auto [mx,pos]=T.query(1,1,n,l,r);
    if(pos!=r)ans=max(ans,T[{pos+1,r}]+mx+Mx);
    if(pos==l)return ;
    if(2*mx<=Mx+T[{l,pos-1}])return ans=max(ans,mx+T[{l,pos-1}]+Mx),void();
    else solvel(l,pos-1,Mx);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // freopen("D.in","r",stdin),freopen("D.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    T.build(1,1,n);
    for(int i=1,opt,x,y,k;i<=q;i++){
        cin>>opt>>x>>y;
        if(opt==1){
            ans=-1e9;
            auto [Mx,Pos]=T.query(1,1,n,x,y);
            solvel(x,Pos-1,Mx),solver(Pos+1,y,Mx);
            if(ans==-1e9)cout<<"No\n";
            else cout<<ans<<'\n';
        }else cin>>k,T.add(1,1,n,x,y,k);
    }
}