题解：P5693 EI 的第六分块

apple_vinegar · 2024-11-10 13:44:17 · 题解

联考上用到了 KTT 这种科技，记录一下。
12.8 update: 减少了很多无用内容，请求通过。

介绍

KTT 是李白天所写的浅谈函数最值的动态维护中的部分内容，其中对复杂度，细节等进行了严谨证明。我在此处以本蒟蒻的理解叙述，若有不足麻烦联系。

应用

与线段树不同，若我们需解决一段形若 ax+b 的式子，每次修改区间的 a 值或 b 值应该怎么处理呢。考虑到维护区间和是简单的，那么我们假设解决如下问题。

1. 将区间 [L,R] 中每个数加上 x，保证 x>0。
1. 查询区间 [L,R] 的最大值。

思路

比起普通的线段树，我们发现在改变了区间值时可能会使区间内最大值变化，导致懒标记难以记录。\ 于是我们此时可以设立一个区间阈值 c 表示两个 ax+b 的图像的交点，即仅当经过此交点时需更新最大值。\ 因为对于线段树上每个区间范围大于其子树，故其阈值（此处看作“受限范围” 可能更好理解）也不大于其子树，所以我们只需要在某个线段树节点达到阈值时重构其子树即可。重构代码如下：

inline void rebuild(int p){
    if(d[p].c>=0) return;//需要更替，即超过阈值时需要重构其子树
    pushdown(p);
    rebuild(ls);
    rebuild(rs);
    up(p);
    return ;
}

转化

这道题是求的区间最大子段和，如何由上述问题转化而来呢？我们不难想到，区间最大子段和可以由合并得到，存储信息如下：

合并方式如下：

lmx= \max (ls.lmx,ls.len+rs.lmx)
rmx= \max (rs.rmx,rs.len+ls.rmx)
totmx= \max ({ls.totmx,rs.totmx,ls.rmx+rs.lmx})
len=ls.len+rs.len

至此，我们已经完成了由最基本的线段树到此题的思路转换，只需注意合并细节即可。

AC Code

#include<bits/stdc++.h>
#define int long long
#define mid ((l+((r-l)>>1)))
#define ls (p<<1)
#define rs (ls|1)
#define lt ls,l,mid
#define rt rs,mid+1,r
#define fi first
#define se second
using namespace std;
const int N=5e6+5,MX=1e18;

inline int read(){
    int a=1,b=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') a=-a;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        b=(b<<1)+(b<<3)+(ch^48);
        ch=getchar();
    }
    return a*b;
}

struct line{
    int a,b;//即kkt最基本的处理方式，表示成ax+b;
    friend line operator +(line a,line b){
        return {a.a+b.a,a.b+b.b};//重载+，合并两个函数
    }
};

struct node{
    line lmx,rmx,totmx,len;//lmx:最大前缀和 rmx:最大后缀和 totmx：最大区间和，即答案 len：区间长度
    int c;//阈值，决定什么时候需要重构子树
};

node d[N<<2];
int tag[N<<2],a[N];

inline pair<line,int> inter(line a,line b){
    if(a.a<b.a||(a.a==b.a&&a.b<b.b)) swap(a,b);//不同与普通的KTT,我们此处需要前缀与后缀，所以不仅需要反馈数值，还需反馈先后顺序
    if(a.b>=b.b) return (make_pair(a,MX));//无交
    return (make_pair(b,(b.b-a.b)/(a.a-b.a)));//交点的x
}

inline node add(node a,node b){
    pair<line,int> tmp;
    node res;
    res.c=min(a.c,b.c);
    tmp=inter(a.lmx,a.len+b.lmx);
    res.lmx=tmp.fi;   //res.lmx=max(a.lmx,a.len+b.lmx)
    res.c=min(res.c,tmp.se);
    tmp=inter(b.rmx,b.len+a.rmx);
    res.rmx=tmp.fi;   //res.rmx=max(b.rmx,b.len+a.rmx)
    res.c=min(res.c,tmp.se);
    tmp=inter(a.totmx,b.totmx);
    res.c=min(res.c,tmp.se);
    tmp=inter(tmp.fi,a.rmx+b.lmx);
    res.totmx=(tmp.fi);   //res.totmx=max({a.totmx,b.totmx,a.rmx+b.lmx})
    res.c=min(res.c,tmp.se);
    res.len=a.len+b.len;   //res.len=a.len+b.len
    return res;
}

inline void up(int p){
    d[p]=add(d[ls],d[rs]);
}

inline void build(int p,int l,int r){
    if(l==r){
        d[p].lmx=d[p].rmx=d[p].totmx=d[p].len={1,a[l]};//初始化最大子段和为自身，长度为1
        d[p].c=MX;//初始阈值设为极大值
        return;
    }
    build(lt),build(rt);
    up(p);
    return ;
}

inline void push(int p,int k){//不用考虑a的变化，可以化为b变化a*x
    tag[p]+=k;
    d[p].c-=k;
    d[p].lmx.b  +=d[p].lmx.a*k;
    d[p].rmx.b  +=d[p].rmx.a*k;
    d[p].totmx.b+=d[p].totmx.a*k;
    d[p].len.b  +=d[p].len.a*k;

    return ;
}

inline void pushdown(int p){
    push(ls,tag[p]),push(rs,tag[p]);
    tag[p]=0;
}

inline void rebuild(int p){
    if(d[p].c>=0) return;//需要更替，即超过阈值时需要重构其子树
    pushdown(p);
    rebuild(ls);
    rebuild(rs);
    up(p);
    return ;
}

inline void update(int p,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y){
        push(p,k);
        rebuild(p);
        return;
    }
    pushdown(p);
    if(x<=mid) update(lt,x,y,k);
    if(y>mid) update(rt,x,y,k);
    up(p);
    return ;
}

inline node query(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return d[p];
    }
    pushdown(p);
    if(y<=mid) return query(lt,x,y);
    if(x>mid) return query(rt,x,y);
    return add(query(lt,x,y),query(rt,x,y));
}

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

后记：没用结构体封装被机房大佬骂了。

做了CF1178G，发现 rebuild 的过程其实就是继续递归，并且若需修改，需要 pushdown 。根据我们之前发现的规律，一个子树若无需修改，其子树受限范围小于它，也无需修改，所以我们完全可以在 update 添加一个条件实现递归以减小码量。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define mid ((l+((r-l)>>1)))
#define ls (p<<1)
#define rs (ls|1)
#define lt ls,l,mid
#define rt rs,mid+1,r
#define fi first
#define se second
using namespace std;
const int N=5e6+5,MX=1e18;

inline int read(){
    int a=1,b=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') a=-a;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        b=(b<<1)+(b<<3)+(ch^48);
        ch=getchar();
    }
    return a*b;
}

struct line{
    int a,b;//即kkt最基本的处理方式，表示成ax+b;
    friend line operator +(line a,line b){
        return {a.a+b.a,a.b+b.b};//重载+，合并两个函数
    }
};

struct node{
    line lmx,rmx,totmx,len;//lmx:最大前缀和 rmx:最大后缀和 totmx：最大区间和，即答案 len：区间长度
    int c;//阈值，决定什么时候需要重构子树
};

node d[N<<2];
int tag[N<<2],a[N];

inline pair<line,int> inter(line a,line b){
    if(a.a<b.a||(a.a==b.a&&a.b<b.b)) swap(a,b);//不同与普通的KTT,我们此处需要前缀与后缀，所以不仅需要反馈数值，还需反馈先后顺序
    if(a.b>=b.b) return (make_pair(a,MX));//无交
    return (make_pair(b,(b.b-a.b)/(a.a-b.a)));//交点的x
}

inline node add(node a,node b){
    pair<line,int> tmp;
    node res;
    res.c=min(a.c,b.c);
    tmp=inter(a.lmx,a.len+b.lmx);
    res.lmx=tmp.fi;   //res.lmx=max(a.lmx,a.len+b.lmx)
    res.c=min(res.c,tmp.se);
    tmp=inter(b.rmx,b.len+a.rmx);
    res.rmx=tmp.fi;   //res.rmx=max(b.rmx,b.len+a.rmx)
    res.c=min(res.c,tmp.se);
    tmp=inter(a.totmx,b.totmx);
    res.c=min(res.c,tmp.se);
    tmp=inter(tmp.fi,a.rmx+b.lmx);
    res.totmx=(tmp.fi);   //res.totmx=max({a.totmx,b.totmx,a.rmx+b.lmx})
    res.c=min(res.c,tmp.se);
    res.len=a.len+b.len;   //res.len=a.len+b.len
    return res;
}

inline void up(int p){
    d[p]=add(d[ls],d[rs]);
}

inline void build(int p,int l,int r){
    if(l==r){
        d[p].lmx=d[p].rmx=d[p].totmx=d[p].len={1,a[l]};//初始化最大子段和为自身，长度为1
        d[p].c=MX;//初始阈值设为极大值
        return;
    }
    build(lt),build(rt);
    up(p);
    return ;
}

inline void push(int p,int k){//不用考虑a的变化，可以化为b变化a*x
    tag[p]+=k;
    d[p].c-=k;
    d[p].lmx.b  +=d[p].lmx.a*k;
    d[p].rmx.b  +=d[p].rmx.a*k;
    d[p].totmx.b+=d[p].totmx.a*k;
    d[p].len.b  +=d[p].len.a*k;

    return ;
}

inline void pushdown(int p){
    push(ls,tag[p]),push(rs,tag[p]);
    tag[p]=0;
}

inline void update(int p,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y&&d[p].c>=k){
        push(p,k);
        return;
    }
    pushdown(p);
    if(x<=mid) update(lt,x,y,k);
    if(y>mid) update(rt,x,y,k);
    up(p);
    return ;
}

inline node query(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return d[p];
    }
    pushdown(p);
    if(y<=mid) return query(lt,x,y);
    if(x>mid) return query(rt,x,y);
    return add(query(lt,x,y),query(rt,x,y));
}

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