P6792 [SNOI2020] 区间和 题解

· · 题解

这篇题解内容比较详细有点长，适合像我这样的初学蒟蒻

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

这题就是 KTT+吉司机，所以建议在做这题之前先去把板题切了：

P5693 EI 的第六分块

P6242 【模板】线段树 3

虽然我是先做的这题，这题代码拷过去改改秒切P5693，双倍经验了属于是。

本篇题解不含复杂度证明

题意很清晰不说了。

吉司机线段树

首先讲操作 0，这取最值的操作一眼吉司机，会的大佬可以直接跳过啦。

我们先考虑一下该操作难点在哪里：因为整个区间里有很多数，我们无法确定哪些是要变的哪些是不变的，变的那些变化多少，这就导致无法快速更新信息，只能暴力的递归到叶子再合并上来，这样复杂度直接爆炸！

那如果整个区间上只有一种数需要被更新呢？那问题不就迎刃而解了！具体而言，我们需要维护三个信息：

当 mn \ge x 时，操作显然是无效的，因为区间里所有数都比操作数大。

当 mn < x < semn 时，这是我们真正需要处理的区间，实际要做的就是令所有最小值加上 x，又因为我们维护了最小值数量，所以这就是一个平凡的区间加操作。

当 x > semn 时，继续向下递归直到找到上述情况，最坏情况就是一直递归到了叶子。

该算法的复杂度是单次更新是 O(\log^2n)，不会证，但肯定能过。

KTT

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

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

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

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

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

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

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

  1. 要么直接继承左区间的答案 即 lmx_{ls}。
  2. 要么考虑更新 那就是左区间和加上右区间前缀 即 sum_{ls} + lmx_{rs}。

rmx 同理。

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 即可。

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

那么所有知识点就都讲完啦！但这题代码巨长很容易写丑，我就是第一遍写完死活调不出来，然后去借鉴了一下题解里两位 dalao 的代码修了修（） 一些细节就放在注释里啦！

代码

#include<bits/stdc++.h>
#define MAXN 100005
#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;
    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 mn,semn;
    long long tag;//tag维护要变成的值 不是变化量哦
    //我最开始写的是变化量（因为之前做过P6242） 然后发现又加又减有很多分类讨论不好写也不好调 所以重构了一遍代码改成要变成的值了 这样可以直接取max
    node convert(){
        node a=*this;
        a.lmx.k=a.rmx.k=a.sum.k=a.totmx.k=0;
        return a;
    }
}t[MAXN<<2];

void add(node &res,node a,node b){
    pair<line,long long> tmp;
    res.x=min(a.x,b.x);
    //sum=ls.sum+rs.sum
    res.sum=a.sum+b.sum;
    //lmax=max(ls.lmax,ls.sum+rs.lmax)
    tmp=max(a.lmx,a.sum+b.lmx);
    res.lmx=tmp.first;
    res.x=min(res.x,tmp.second);
    //rmax=max(rs.rmax,rs.sum+ls.rmax)
    tmp=max(b.rmx,b.sum+a.rmx);
    res.rmx=tmp.first;
    res.x=min(res.x,tmp.second);
    //totmax=max(ls.totmax,rs.totmax,ls.rmax+rs.lmax)
    tmp=max(a.totmx,b.totmx);
    res.x=min(res.x,tmp.second);
    tmp=max(tmp.first,a.rmx+b.lmx);
    res.totmx=tmp.first;
    res.x=min(res.x,tmp.second);
}
/*
这个地方如果你把吉司机要维护的值和KTT分开其实重载运算符很方便的
当然也可以令一个tmp把属于吉司机的信息记一下 更新完KTT之后再还原现场
总之就是如果把所有信息都封装在一起了 注意更新KTT的时候别把吉司机搞没了就行
*/

void pushup(int k){
    if(t[ls].mn==t[rs].mn){
        t[k].semn=min(t[ls].semn,t[rs].semn);
        t[k].mn=t[ls].mn;
        add(t[k],t[ls],t[rs]);
    }else if(t[ls].mn<t[rs].mn){
        t[k].semn=min(t[ls].semn,t[rs].mn);
        t[k].mn=t[ls].mn;
        add(t[k],t[ls],t[rs].convert());//打过吉司机的都知道吧 只有最值参与区间修改 所以肯定是最值在哪一个儿子上就要哪个的信息啊 这里的k可以感性理解一下吉司机的mncnt 为了方便暂时把另一个清空就行
    }else{
        t[k].semn=min(t[ls].mn,t[rs].semn);
        t[k].mn=t[rs].mn;
        add(t[k],t[ls].convert(),t[rs]);
    }
}

void build(int k,int l,int r){
    t[k].l=l;t[k].r=r;
    t[k].tag=-inf;//因为是维护的变成哪个值要取max所以是-inf 维护变化量的不用管
    if(l==r){
        line tmp={1,A[l]};
        t[k].lmx=t[k].rmx=t[k].sum=t[k].totmx=tmp;
        t[k].x=inf;
        t[k].mn=A[l];
        t[k].semn=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){
    if(t[k].mn>=v) return;
    long long tmp=v-t[k].mn;
    t[k].mn=v;
    t[k].tag=max(t[k].tag,v);
    t[k].sum.add(tmp);
    t[k].totmx.add(tmp);
    t[k].lmx.add(tmp);
    t[k].rmx.add(tmp);
    t[k].x-=tmp;
}

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

void upd(int k,long long v){
    t[k].tag=max(t[k].tag,v);
    long long tmp=v-t[k].mn;
    if(tmp>t[k].x){//超过阈值啦！ 直接重构
        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].mn>=v) return;
    if(t[k].l>=l && t[k].r<=r && t[k].semn>v){//之前打吉司机错过这里 注意是>不是>= 不然次小值就不严格啦！
        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);
    node res;
    res=res.convert();//像我这种写法要注意这里初始化要写好哦 不然会收获一份样例能过但WA0pts的代码
    add(res,query(ls,l,r),query(rs,l,r));
    return res;
}

int main(){
//  freopen("P6792.in","r",stdin);
//  freopen("P6792.out","w",stdout);
    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==0){
            x=read();
            update(1,l,r,x);
        }else{
            long long ans=query(1,l,r).totmx.b;
            printf("%lld\n",max(0ll,ans));//注意题面上说可以取空集！ 所以一定要和0取一下max 我因为这个点WA75pts调了好久QwQ
        }
    }
    return 0;
}
//一点小建议：样例给的比较弱只有全局查询 调不出来的宝子可以自己造点有区间查询的数据 或者用小数据拍一拍什么的