P5693 EI 的第六分块 题解

· · 题解

第二分块怎么就比第六分块简单了 第六分块明明好懂好写 我为第六分块正名！

第六分块不用分块。

本篇题解大部分内容跟我的P6792 [SNOI2020] 区间和 题解存在重复，因为我是先写的那道题然后来板题拿的双倍经验。

KTT 维护区间最大子段和板题，本篇题解不含复杂度证明。

学习过程中参考了楼上 dalao 的题解以及EI的博客。

求区间最大子段和，先考虑在线段树上的暴力做法。

朴素的线段树做法是维护四个信息：

怎么维护呢？有以下式子：

解释一下 考虑最大子段和一共有三种情况：

  1. 子段全部位于左区间内 即 totmx_{ls}。
  2. 子段全部位于右区间内 即 totmx_{rs}。
  3. 子段横跨两个区间 这时候左右区间都要做贡献 因为要保证子段连续 所以是 rmx_{1s} + lmx_{rs}。

求 totmx 的方式也解释了为什么要维护 lmx 和 rmx。

对于 lmx 只要强制包含左端点就行啦:

  1. 要么直接继承左区间的答案 即 lmx_{ls}。
  2. 要么考虑更新 那就是左区间和加上右区间前缀 即 sum_{ls} + lmx_{rs}。
$sum$ 太基础没啥好说的。 分析一下该算法的复杂度，因为你每次更新都可能会改变最大子段的构成，这个决策改变之后所有维护的信息都要变，也就是在最劣情况下我们需要重构整棵线段树，即 $O(n)$，查询的话就是 $O(\log n)$ 的，所以整体还是比暴力要优，对于一些查询多的题说不定也能冲过去。 现在考虑该算法瓶颈，不难发现在于**修改会改变最大子段构成的决策**，但手推几组数据也很容易发现，不是所有修改都会对决策有影响，只有当变化量大于某个阈值时才会改变决策，否则该是哪个子段还是哪个子段，当成平凡的区间加维护就好。 我们考虑将每个值维护成一次函数的形式 $y=kx+b$，用一个二元组 $(k,b)$ 来表示，$b$ 是现在的值，$k$ 是最大子段的长度，$x$ 即为变化量，在取 $\max$ 时，以前我们只需比较 $b$ 的大小就够了（$x=0$），现在我们还要维护一下什么时候这个决策会改变，具体来说: 两条直线 $l1$，$l2$，不妨令 $b_{l1} > b_{l2}
  2. 否则 阈值就是两条直线交点的横坐标。

这部分的代码： 

pair<line,long long> max(line a,line b){
    if(a.k<b.k || (a.k==b.k && a.b<b.b)) swap(a,b);
    if(a.b>=b.b) return mkp(a,inf);
    else return mkp(b,(b.b-a.b)/(a.k-b.k));
}

易知 totmx，lmx 和 rmx 中任何一个改变都可能影响到最终决策，所以整个节点的阈值对它们产生的三个阈值取 \min 即可。

这部分代码：

node operator + (const node &a) const{
    node res;
    pair<line,long long> tmp;
    res.x=min(x,a.x);
    //sum=ls.sum+rs.sum
    res.sum=sum+a.sum;
    //lmax=max(ls.lmax,ls.sum+rs.lmax)
    tmp=max(lmx,sum+a.lmx);
    res.lmx=tmp.first;
    res.x=min(res.x,tmp.second);
    //rmax=max(rs.rmax,rs.sum+ls.rmax)
    tmp=max(a.rmx,a.sum+rmx);
    res.rmx=tmp.first;
    res.x=min(res.x,tmp.second);
    //totmax=max(ls.totmax,rs.totmax,ls.rmax+rs.lmax)
    tmp=max(totmx,a.totmx);
    res.x=min(res.x,tmp.second);
    tmp=max(tmp.first,rmx+a.lmx);
    res.totmx=tmp.first;
    res.x=min(res.x,tmp.second);
    return res;
}

具体的复杂度证明去 EI 大佬的博客看吧，蒟蒻不会分析势能 QwQ

代码直接用P6792 [SNOI2020] 区间和的代码改了改（） 一些细节问题放注释里啦！

#include<bits/stdc++.h>
#define MAXN 400005
#define inf 1e18
#define ls k<<1
#define rs k<<1|1
#define mkp make_pair
using namespace std;

inline long long read(){
    long long x=0;
    int f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

int n,q;
long long A[MAXN];

//一次函数
struct line{
    long long k,b;//b可以认为就是正常的值 跟原来不加一次函数优化是一样的 k即最大子段和这个子段的长度
    line operator + (const line &a) const{
        return (line){k+a.k,b+a.b};
    }
    void add(long long v){
        b+=k*v;
    }
};

pair<line,long long> max(line a,line b){
    if(a.k<b.k || (a.k==b.k && a.b<b.b)) swap(a,b);
    if(a.b>=b.b) return mkp(a,inf);
    else return mkp(b,(b.b-a.b)/(a.k-b.k));
}

struct node{
    int l,r;
    line lmx,rmx,sum,totmx;
    long long x;//阈值
    long long tag;
    node operator + (const node &a) const{//维护最大子段和需要的四个变量 同时维护阈值
        node res;
        pair<line,long long> tmp;
        res.x=min(x,a.x);
        //sum=ls.sum+rs.sum
        res.sum=sum+a.sum;
        //lmax=max(ls.lmax,ls.sum+rs.lmax)
        tmp=max(lmx,sum+a.lmx);
        res.lmx=tmp.first;
        res.x=min(res.x,tmp.second);
        //rmax=max(rs.rmax,rs.sum+ls.rmax)
        tmp=max(a.rmx,a.sum+rmx);
        res.rmx=tmp.first;
        res.x=min(res.x,tmp.second);
        //totmax=max(ls.totmax,rs.totmax,ls.rmax+rs.lmax)
        tmp=max(totmx,a.totmx);
        res.x=min(res.x,tmp.second);
        tmp=max(tmp.first,rmx+a.lmx);
        res.totmx=tmp.first;
        res.x=min(res.x,tmp.second);
        return res;
    }
}t[MAXN<<2];

void pushup(int k){
    node tmp=t[ls]+t[rs];//重载的运算符只维护了KTT 别把除KTT之外的正常线段树信息搞没了
    tmp.tag=t[k].tag;
    tmp.l=t[k].l;
    tmp.r=t[k].r;
    t[k]=tmp;
}

void build(int k,int l,int r){
    t[k].l=l;t[k].r=r;
    if(l==r){
        line tmp={1,A[l]};//初始值最大子段就是本身 子段长度为1
        t[k].lmx=t[k].rmx=t[k].sum=t[k].totmx=tmp;
        t[k].x=inf;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(k);
}

void calc(int k,long long v){
    t[k].tag+=v;
    t[k].sum.add(v);
    t[k].totmx.add(v);
    t[k].lmx.add(v);
    t[k].rmx.add(v);
    t[k].x-=v;//别忘了维护阈值
}

void pushdown(int k){
    if(t[k].tag){
        calc(ls,t[k].tag);
        calc(rs,t[k].tag);
        t[k].tag=0;
    }
}

void upd(int k,long long v){
    if(v>t[k].x){//超过阈值的递归重构子树
        v+=t[k].tag;
        t[k].tag=0;
        upd(ls,v);
        upd(rs,v);
        pushup(k);
    }else{
        calc(k,v);//没超过阈值就是平凡的区间加
    }
}

void update(int k,int l,int r,long long v){
    if(t[k].l>=l && t[k].r<=r){
        upd(k,v);
        return;
    }
    pushdown(k);
    int mid=(t[k].l+t[k].r)>>1;
    if(mid>=l){
        update(ls,l,r,v);
    }
    if(mid<r){
        update(rs,l,r,v);
    }
    pushup(k);
}

node query(int k,int l,int r){
    if(t[k].l>=l && t[k].r<=r){
        return t[k];
    }
    pushdown(k);
    int mid=(t[k].l+t[k].r)>>1;
    if(mid>=r) return query(ls,l,r);
    if(mid<l) return query(rs,l,r);
    return query(ls,l,mid)+query(rs,mid+1,r);
}

int main(){
    n=read();q=read();
    for(int i=1;i<=n;i++){
        A[i]=read();
    }
    build(1,1,n);
    int op,l,r;
    long long x;
    while(q--){
        op=read();
        l=read();r=read();
        if(op==1){
            x=read();
            update(1,l,r,x);
        }else{
            long long ans=query(1,l,r).totmx.b;
            printf("%lld\n",max(0ll,ans));
        }
    }
    return 0;
}