P6792 [SNOI2020] 区间和

· · 题解

如果只有操作 0 或者操作 1，那么这个问题是容易解决的。

如果有操作 0，那么直接写吉司机线段树就行了，而如果只有后面的东西就是很板的线段树合并题目。

为了防止我忘记怎么写吉司机，如果 mn\ge x 那么无意义返回，如果 mn<x<se 那么 mn=x 然后返回，对于其他情况继续递归就对了。

考虑怎么为 mn<x<se 的时候维护这个经典的线段树合并的信息。

对于这个经典的线段树合并操作，我们需要维护包含左端点的最大和 lmx，包含右端点的最大和 rmx，最后是这个节点的贡献 ans。

那么要计算 ans 有公式：

ans(rt)=\max\{ans(ls),ans(rs),rmx(ls)+lmx(rs)\}

所以我们需要快速的确定其儿子的 lmx 和 rmx 值才能打懒惰标记，因为 lmx 和 rmx 具有对称性所以下面只考虑 lmx 操作。

如果 lmx 和 ans 的区间没有不改变，那么区间 \max 的影响是容易计算计算的。

我们只需要记录这个区间中有多少最小值就可以快速计算了，自然的想到考虑什么时候其区间不会改变。

考虑下面一个情况，假设现在 lmx 的区间的紫色，容易理解经过区间 \max 操作是永远不可能取到橙色区间的，因为给橙色区间造成的贡献也会反应到紫色区间身上，然而本来选择的区间的紫色的，所以紫色拥有而橙色不拥有的区间肯定是答案造成了正面贡献的。

进一步的，我们得到了右端点经过 \max 操作只会增加，于是总共的增加次数最大只有 O(n\log n)，这是一个很优秀的性质。

需要注意即使修改操作并没有包含整个区间因为其只会增加区间和所以 lmx 的右端点依然不会向左，这是容易理解的。

假设紫色区间和红色区间的和为分别为 S_1 和 S_2，其中包含的最小值个数分别为 M_1 和 M_2，那么红色区间的想要超过紫色区间所受到的区间 \max 的值 V 和原本的最大值 mx 的差 \Delta，也就是 V-mx 应该满足：

\Delta\ge \dfrac{S_1-S_2}{M_2-M_1}

需要注意如果 M_1=M_2，那么红色区间永远都不可能超过紫色区间。

那么我们可以维护区间中阈值的最小值，然后将 \Delta 进行累加，当 \Delta 超过这个阈值时就进行类似于吉司机的操作进行直接向下遍历不进行返回最后 pushup 就行了。

考虑证明这样操作的复杂度的正确性，因为一次暴力的更改 lmx 只会遍历其所有的祖先而后移操作又是一个罕见操作，所以总共的时间复杂度就是 O(n\log ^2 n)。

于是我们就得到了 O((q+n)\log ^2n) 的优秀做法，但是非常难写。

最后感谢 zzq 老师在很久以前的讲解，在视频里学习了思路。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=0x3f3f3f3f3f3f3f3f;
int n,q,a[N];
struct Seg{
    struct node{
        int v,ct;node(){v=-inf,ct=0;}node(int k,int V) {v=k,ct=V;}
        friend bool operator<(node a,node b){return a.v<b.v;}
        friend node operator+(node a,node b){return{a.v+b.v,a.ct+b.ct};}
        void ADD(int k){v+=k*ct;}
    };
    struct Node{
        int mn,smn,lazy,Min;node sum,pre,suf,ans;
        void EMP(){mn=smn=Min=inf,sum=pre=suf=ans={0,0},lazy=-inf;}
        void set(int V){mn=lazy=V,Min=smn=inf,sum=pre=suf=ans={V,1};}
        void ck_mn(int k){if(mn!=k) sum.ct=pre.ct=suf.ct=ans.ct=0; }
    }s[N<<2];
    int G(node A,node B){if(B.ct<=A.ct) return inf;return (A.v-B.v)/(B.ct-A.ct);}
    Node pushup(Node X,Node Y){
        Node A;A.EMP();
        A.mn=min(X.mn,Y.mn),A.smn=min(X.smn,Y.smn);
        if(X.mn<Y.mn) A.smn=min(A.smn,Y.mn);
        if(Y.mn<X.mn) A.smn=min(A.smn,X.mn);
        X.ck_mn(A.mn),Y.ck_mn(A.mn),A.sum=X.sum+Y.sum;
        A.ans=max({X.ans,Y.ans,X.suf+Y.pre});
        A.pre=max(X.pre,X.sum+Y.pre),A.suf=max(Y.suf,Y.sum+X.suf);
        A.Min=min({G(A.pre,X.sum+Y.pre),G(A.suf,Y.sum+X.suf)});
        A.Min=min({A.Min,G(A.ans,X.ans),G(A.ans,Y.ans),G(A.ans,X.suf+Y.pre)});
        A.Min=min({A.Min+A.mn,X.Min,Y.Min});
        return A;
    }
    void PUTTAG(int k,int V){
        s[k].sum.ADD(V-s[k].mn),s[k].ans.ADD(V-s[k].mn);
        s[k].pre.ADD(V-s[k].mn),s[k].suf.ADD(V-s[k].mn);
        s[k].mn=s[k].lazy=V;
    }
    void pushdown(int k,int l,int r){
        int mid=(l+r)/2;
        zkw(k*2,l,mid,s[k].lazy);
        zkw(k*2+1,mid+1,r,s[k].lazy); 
        s[k].lazy=-inf;
    }
    void zkw(int k,int l,int r,int V){
        if(s[k].mn>=V) return;
        if(s[k].smn>V&&V<s[k].Min){
            PUTTAG(k,V);
            return;
        }
        s[k].lazy=V,pushdown(k,l,r);
        s[k]=pushup(s[k*2],s[k*2+1]);
    }
    void build(int k,int l,int r){
        s[k].EMP();
        if(l==r){s[k].set(a[l]);return;}
        int mid=(l+r)>>1;
        build(k*2,l,mid); 
        build(k*2+1,mid+1,r);
        s[k]=pushup(s[k*2],s[k*2+1]);
    }
    void change(int k,int l,int r,int x,int y,int V){
        if(x<=l&&r<=y){
            if(s[k].mn>=V) return;
            if(s[k].smn>V&&V<s[k].Min){PUTTAG(k,V);return;}
        }
        if(r<x||y<l) return;
        int mid=(l+r)/2;
        pushdown(k,l,r);
        change(k*2,l,mid,x,y,V);
        change(k*2+1,mid+1,r,x,y,V);
        s[k]=pushup(s[k*2],s[k*2+1]);
    }
    Node ask(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y) return s[k];
        int mid=(l+r)/2;
        pushdown(k,l,r);
        if(y<=mid) return ask(k*2,l,mid,x,y);
        if(x>=mid+1) return ask(k*2+1,mid+1,r,x,y);
        return pushup(ask(k*2,l,mid,x,y),ask(k*2+1,mid+1,r,x,y));
    }
}tr;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    tr.build(1,1,n);
    for(int i=1,op,x,y,z;i<=q;i++){
        cin>>op>>x>>y;
        if(!op){
            cin>>z;
            tr.change(1,1,n,x,y,z);
        }
        else{
            cout<<max(tr.ask(1,1,n,x,y).ans.v,0ll)<<'\n';
        }
    }
    return 0;
}