题解：P5693 EI 的第六分块

· · 题解

这种高级数据结构还是太抽象了，简单理一下思路，不会 KTT 的应该看不懂。

只考虑区间查的问题，我们显然维护区间和、最大前缀和、最大后缀和，以及答案。

然后考虑这样一件事情：区间如果选择了加 x，那么是不是我们在某种情况下可以不重构相关节点呢，而且这样对答案没有影响。

我们考虑把问题转化：把上述的四个需要维护值看做一个一次函数。

实际上，我们可以将区间长度看做斜率 k，然后加法标记看做自变量 x，再将原答案看做 b。

最基础的，每次我们考虑合并两条直线，这个贪心搞一搞就行了很简单。

我们在线段树的每个节点上维护一个阈值 lim 表示如果加法标记 x \ge lim 那么至少需要更新一个信息。

然后就是合并两个节点的分类讨论，可以看代码，去掉直线合并和阈值实际上和不带修差不多。

打标记的时候考虑这样一件事：不妨把这个阈值看做一个限制值，意思是如果这个值小于等于 0 我们就需要递归子树修改，反之直接修改并返回。

然后就是线段树基础结构的套用，经过复杂度分析之后是 O((n+m) \log ^3 n)。细节我看不懂，可以看一下其他题解提供的论文。

注意，由于子序列可以为空所以答案需要对 0 取最大值。当然我相信这种问题其实没必要提出来。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+5,inf=1e18;
struct line{
    int k,b;
    line operator +(const line &x)const{return (line){k+x.k,b+x.b};}
};
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 ans1,sum,lsum,rsum;int lim;
    Point operator +(const Point &x)const{
        Point ans;ans.lim=min(lim,x.lim);ans.sum=sum+x.sum;
        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.ans1=lq.first,ans.lim=min(ans.lim,lq.second);return ans;
    } 
}c[N<<2];
int n,a[N],q,l,r,op,x,m,k;
void updata(int x){c[x]=c[x<<1]+c[x<<1|1];}
void build(int x,int l,int r){
    if(l==r){line tmp=(line){1ll,a[l]};
        c[x]=(Point){tmp,tmp,tmp,tmp,inf};
        return;
    }int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);updata(x);
}int tag[N<<2];
void xg(int x,int y){
    tag[x]+=y;c[x].lim-=y;
    c[x].ans1.b+=c[x].ans1.k*y,c[x].lsum.b+=c[x].lsum.k*y;
    c[x].rsum.b+=c[x].rsum.k*y,c[x].sum.b+=c[x].sum.k*y;
}
void pushdown(int x,int l,int r,int k){
    if(k>c[x].lim){
        int mid=(l+r)>>1;
        pushdown(x<<1,l,mid,tag[x]+k);
        pushdown(x<<1|1,mid+1,r,tag[x]+k);
        updata(x);tag[x]=0;
    }else xg(x,k);
}
void down(int x){
    xg(x<<1,tag[x]);
    xg(x<<1|1,tag[x]);tag[x]=0;
}
void change(int x,int l,int r,int s,int t,int k){
    if(l>=s&&r<=t){
        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];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(0);
    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==1){
            cin >> k;
            change(1,1,n,l,r,k);
        }else cout << max(0ll,query(1,1,n,l,r).ans1.b) << "\n";
    }
    return 0;
}