题解：P5693 EI 的第六分块

· · 题解

尖端科技 KTT，用了都说好。

简介

KTT 是 EntropyIncreaser 巨佬提出的用于特定问题的全新数据结构，它有啥强大功能呢？我们都知道普通线段树可以支持区间加与区间最值查询，但是当每个点增量不同的时候，普通线段树就无能为力了。此时，我们的 KTT 出现了！

具体而言，KTT 是一类特殊的很厉害的线段树，每个节点维护一个一次函数 y=ax+b，每次对着 x 修改，这样你通过改变 a 的值可以使得 x 增加相同量的时候真实值变化量不同，而这个节点的真实值储存在 b 中。

相较于普通线段树，KTT 有如下 2 个最大的限制：

  1. 只支持加正数。
  2. 只支持区间查询最大值。

为什么呢？讲完 KTT 的实现你自然就知道了。

实现

KTT 最高妙的地方在于其需要维护一个叫做阈值的东西用于更新最大值。

请看下图，其中红色线的解析式是 y=x+5，绿色线的解析式是 y=2x+1。而我要维护的是这两条线最大值的解析式。明显在 x \in [0,4) 这段最大值的解析式是 y=x+5，而在 x \in [4,\infty) 这段最大值的解析式是 y=2x+1。所以在 x=4 时发生了一次最大值的更替，我们的阈值就是为了处理出这个更替发生的时间，阈值明显就是左右子树解析式交点的 x 坐标（注意向上取整）。

好，我们现在知道了更替什么时候发生了，而在一次更替发生时我们需要做的就是递归子树，找出是哪条线成为了新的最大值，然后 pushup 更新。

这个递归子树的操作实际上是重构子树，我们将其命名为 rebuild。其他操作与普通线段树差别不大，不过注意，pushdown 操作可能会让子树越过阈值，pushdown 完后要看需不需要 rebuild。

好了，现在你会了一个最板的 KTT，借用一下 Dark_moon 巨佬的出的【模板】KTT，大家可以用来练手。

模板题的 AC 代码扔这里了。

至于前面提出的两个限制，稍微思考一下也很好理解了。你维护的是最大值更替的阈值，而当 x 加的是个负数，很可能会出现回退的情况，而你并不能处理。

本题

现在来看看本题怎么用 KTT 做。

首先不带修最大子段和这个东西可以简单地线段树维护每个节点覆盖区间的最大前缀、最大后缀、所有数的总和、最大子段和，然后合并得到。如果你不会的话可以去做 P4513 小白逛公园。

然后考虑修改，观察到区间加的 x 范围是 1 \le x \le 10^{6}，这很 KTT。想一下区间可以怎么用一次函数的形式表示。一个区间长度为 len 的区间加上一个 k，贡献是 len \times k，所以你的一次函数 y=ax+b 的 a 就是区间长度，这个区间的真实值储存在 b 中。

想到这里就做完了，只需要在模板的基础上更改一下合并操作就行了。

时间复杂度的话，本人太菜了，并不会分析。据说是三只 \log 的，但很难卡满，可以当作两只 \log 来算。有兴趣的童鞋可以去看 EI 的证明。

AC code：

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f
using namespace std;
const int N=400010;
struct csq{
    int a,b;
    friend csq operator +(csq x,csq y){//重载一下两个函数的合并，显然b是直接相加，而a是与区间长度相关的，合并也是直接相加
        return (csq){x.a+y.a,x.b+y.b};
    }
};
pair<csq,int> inter(csq x,csq y){//不仅需要知道阈值是多少，你还需要知道是哪个函数
    if(x.b==y.b){
        if(x.a<y.a)return make_pair(y,inf);
        else return make_pair(x,inf);
    }
    if(x.b<y.b){
        if(x.a<=y.a)return make_pair(y,inf);
        else return make_pair(y,(x.b-y.b)/(y.a-x.a));
    }
    else{
        if(x.a>=y.a)return make_pair(x,inf);
        else return make_pair(x,(y.b-x.b)/(x.a-y.a));
    }
}
struct zyx{
    csq lmax,rmax,sum,ans;
    int intr;
    friend zyx operator +(zyx x,zyx y){//实际上就是线段树的合并操作
        zyx temp;
        pair<csq,int> t1,t2,t3,t4;
        t1=inter(x.lmax,x.sum+y.lmax);
        t2=inter(y.rmax,x.rmax+y.sum);
        t3=inter(x.ans,y.ans);
        t4=inter(t3.first,x.rmax+y.lmax);
        temp.intr=min({x.intr,y.intr,t1.second,t2.second,t3.second,t4.second});
        temp.lmax=t1.first;
        temp.rmax=t2.first;
        temp.ans=t4.first;
        temp.sum=x.sum+y.sum;
        return temp;
    } 
}w[N<<2];
int n,q,a[N],lazy[N<<2];
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void build(int u,int l,int r){
    if(l==r){
        w[u].lmax=(csq){1,a[l]};
        w[u].rmax=(csq){1,a[l]};
        w[u].sum=(csq){1,a[l]};
        w[u].ans=(csq){1,a[l]};//其他所有值的初始化：区间长度为1，值为a[l]
        w[u].intr=inf;//阈值初始化为inf
        return;
    }
    int mid=(l+r)>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    w[u]=w[u*2]+w[u*2+1];
}
void make_tag(int u,int k){//标准的打标记操作
    w[u].sum.b+=w[u].sum.a*k;
    w[u].ans.b+=w[u].ans.a*k;
    w[u].lmax.b+=w[u].lmax.a*k;
    w[u].rmax.b+=w[u].rmax.a*k;//现在你每个节点的值就是b了，区间长度为a，区间中每个数加上k，贡献就是a*k
    w[u].intr-=k;//注意！更新阈值
    lazy[u]+=k;
}
void pushdown(int u){
    make_tag(u*2,lazy[u]);
    make_tag(u*2+1,lazy[u]);
    lazy[u]=0;
}
void rebuild(int u){
    if(w[u].intr>=0)return;
    pushdown(u);
    rebuild(u*2);
    rebuild(u*2+1);
    w[u]=w[u*2]+w[u*2+1];
}
void update(int u,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y){
        make_tag(u,k);
        rebuild(u);
        return;
    }
    pushdown(u);
    int mid=(l+r)>>1;
    if(x<=mid)update(u*2,l,mid,x,y,k);
    if(y>mid)update(u*2+1,mid+1,r,x,y,k);
    w[u]=w[u*2]+w[u*2+1];
}
zyx query(int u,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return w[u];
    }
    pushdown(u);
    int mid=(l+r)>>1;
    if(x<=mid&&y>mid)return query(u*2,l,mid,x,y)+query(u*2+1,mid+1,r,x,y);
    else if(x<=mid)return query(u*2,l,mid,x,y);
    else if(y>mid)return query(u*2+1,mid+1,r,x,y);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(q--){
        int op=read(),l=read(),r=read();
        if(op==1){
            int x=read();
            update(1,1,n,l,r,x);
        }
        else{
            cout<<max(0ll,query(1,1,n,l,r).ans.b)<<'\n';
            //注意可以不选
        }
    }
    return 0;
}