题解：P6792 [SNOI2020] 区间和

· · 题解

这个题实际上和 P5693 没什么两样。

对于操作一，显然我们可以用吉司机线段树维护最小值以及严格次小值。

然后修改时下传标记等价于区间加上标记与最小值的差，这样就把问题转化为了区间加一个正整数。

利用 KTT，我们维护以变化的数个数作为斜率的直线，也就是更改了原题定义。

我们同时使用吉司机线段树和 KTT 来完成维护过程，但是注意需要保证在合并节点的同时 KTT 需要考虑吉司机线段树的最小值，需要清空一下两者间较大值位置的信息，因为我们修改了定义，所以这里变化的数就清 0。

时间复杂度不会证明，但是想来应该也就是 O((n+m)\log ^3 n) 级别。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,inf=1e18;
int n,a[N],m,l,r,op,x;
struct line{
    int k,b;
    line operator + (const line &x)const{return (line){k+x.k,b+x.b};}
    void set(){k=0;}
    void add(int x){b+=k*x;}
};
pair<line,int> max(line x,line y){
    if(x.k<y.k||(x.k==y.k&&x.b<y.b))swap(x,y);
    if(x.b>=y.b)return make_pair(x,inf);
    return make_pair(y,(y.b-x.b)/(x.k-y.k));
}
struct Point{
    line sum,ans1,lsum,rsum;int lim;
    Point operator + (const Point &x)const{
        Point ans;ans.sum=sum+x.sum;ans.lim=min(lim,x.lim);
        pair<line,int> lq=max(lsum,sum+x.lsum);
        ans.lsum=lq.first,ans.lim=min(ans.lim,lq.second);
        lq=max(x.rsum,rsum+x.sum);ans.rsum=lq.first,ans.lim=min(ans.lim,lq.second);
        lq=max(ans1,x.ans1);ans.lim=min(ans.lim,lq.second);
        lq=max(lq.first,rsum+x.lsum);ans.lim=min(ans.lim,lq.second);ans.ans1=lq.first;return ans;
    }Point set(){
        Point now=*this;
        now.sum.set();now.ans1.set();now.lsum.set();now.rsum.set();return now;
    }void add(int x){sum.add(x),lsum.add(x),rsum.add(x),ans1.add(x);}
};
struct tree{
    Point x;
    int minn,smin;
}c[N<<2];int tag[N<<2];
void updata(int x){
    c[x].minn=min(c[x<<1].minn,c[x<<1|1].minn);
    if(c[x<<1].minn==c[x<<1|1].minn)c[x].smin=min(c[x<<1].smin,c[x<<1|1].smin),c[x].x=c[x<<1].x+c[x<<1|1].x;
    else if(c[x<<1].minn>c[x<<1|1].minn)c[x].smin=min(c[x<<1].minn,c[x<<1|1].smin),c[x].x=c[x<<1].x.set()+c[x<<1|1].x;
    else c[x].smin=min(c[x<<1].smin,c[x<<1|1].minn),c[x].x=c[x<<1].x+c[x<<1|1].x.set();
}
void build(int x,int l,int r){
    tag[x]=-inf;
    if(l==r){line tmp=(line){1,a[l]};
        c[x].x=(Point){tmp,tmp,tmp,tmp,inf};
        c[x].minn=a[l],c[x].smin=inf;return;
    }int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);updata(x);
}
void xg(int x,int k){
    if(c[x].minn>=k)return;int val=k-c[x].minn;
    c[x].minn=k,tag[x]=max(tag[x],k);c[x].x.lim-=val;
    c[x].x.add(val);
}
void pushdown(int x,int l,int r,int k){tag[x]=max(tag[x],k);
    if(k-c[x].minn>c[x].x.lim){
        int mid=(l+r)>>1;
        pushdown(x<<1,l,mid,k);pushdown(x<<1|1,mid+1,r,k);updata(x);
    }else xg(x,k);
}void down(int x){
    if(tag[x]==-inf)return;
    xg(x<<1,tag[x]);xg(x<<1|1,tag[x]);tag[x]=-inf;
}
void change(int x,int l,int r,int s,int t,int k){
    if(c[x].minn>=k)return;
    if(l>=s&&r<=t&&c[x].smin>k){
        pushdown(x,l,r,k);
        return;
    }int mid=(l+r)>>1;down(x);
    if(s<=mid)change(x<<1,l,mid,s,t,k);
    if(t>mid)change(x<<1|1,mid+1,r,s,t,k);updata(x);
}
Point query(int x,int l,int r,int s,int t){
    if(l>=s&&r<=t)return c[x].x;int mid=(l+r)>>1;down(x);
    if(s>mid)return query(x<<1|1,mid+1,r,s,t);
    else{
        if(t<=mid)return query(x<<1,l,mid,s,t);
        return query(x<<1,l,mid,s,t)+query(x<<1|1,mid+1,r,s,t);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)cin >> a[i];build(1,1,n);
    for(int i = 1;i <= m;i++){
        cin >> op >> l >> r;
        if(op==0)cin >> x,change(1,1,n,l,r,x);
        else cout << max(0ll,query(1,1,n,l,r).ans1.b) << "\n";
    }
    return 0;
}