题解：P5693 EI 的第六分块

YZren · 2025-06-26 21:07:54 · 题解

EI 的第六分块

题目大意

给定一个长度为 n 的整数序列，支持两种操作：

区间加一个正数
查询区间最大子段和（可以为空）

解题思路

本题需要使用一种称为 KTT（Kinetic Tournament Tree） 的数据结构来解决。KTT 是线段树的一种变体，能够高效处理区间加正数和区间查询问题。

KTT 的核心思想

KTT 维护的每个节点包含一个一次函数 y = k \times val + b，其中：

每次区间加操作相当于对 b 进行修改：b = b + k \times val。

维护的信息

每个节点需要维护以下信息：

sum：区间和
lmax：从左端点开始的最大子段和
rmax：从右端点开始的最大子段和
max：区间最大子段和
limit：一个阈值，用于判断何时需要更新最大值

合并区间

合并两个子区间时，需要注意顺序，并正确计算各个值：

lmax：取左子区间的 lmax 或左子区间的 sum 加上右子区间的 lmax 中的较大值
rmax：取右子区间的 rmax 或右子区间的 sum 加上左子区间的 rmax 中的较大值
max：取左子区间的 max、右子区间的 max 或左子区间的 rmax 加上右子区间的 lmax 中的最大值
sum：左右子区间 sum 的和

Code

node operator +(const node &a){
        node ans; ans.limit=std::min(limit,a.limit);
        std::pair<line,int> tmp=getmax(lmax,sum+a.lmax);
        ans.lmax=tmp.first;
        ans.limit=std::min(ans.limit,tmp.second);
        tmp=getmax(a.rmax,rmax+a.sum);
        ans.rmax=tmp.first;
        ans.limit=std::min(ans.limit,tmp.second);
        tmp=getmax(max,a.max);
        ans.limit=std::min(ans.limit,tmp.second);
        tmp=getmax(tmp.first,rmax+a.lmax);
        ans.max=tmp.first;
        ans.limit=std::min(ans.limit,tmp.second);
        ans.sum=sum+a.sum;
        return ans;

    }

维护 `limit`

limit 表示需要更新最大值的最小 val 增量。在合并区间时，需要计算所有可能的一次函数交点，并取其中的最小值作为新的 limit。

第一种情况（交点是正数，所以 limit 可以更新）。
第二种情况（两条直线平行没有交点（交点是负数也一样），返回正无穷让其不更新）。

取这个交点就很简单了（注意还要返回先交替的直线，也就是下面那一条）。

Code

std::pair<line,int> getmax(line n1,line n2){
    if(n1<n2) std::swap(n1,n2);
    if(n1.b>=n2.b) return std::make_pair(n1,LLONG_MAX);
    return std::make_pair(n2,(n1.b-n2.b)/(n2.k-n1.k));
}

区间更新

和普通的线段树的过程差不多。

先看标记下传的实现。

Code

struct line{
    int k,b;
    line operator +(const line &a){return (line){k+a.k,b+a.b};}
    void operator +=(const int &a){b+=k*a;}
    bool operator <(const line &a){return (k<a.k||(k==a.k&&b<a.b));}
};

struct node{
    line sum,lmax,rmax,max;
    int limit;
    void operator +=(const int &a){sum+=a;lmax+=a;rmax+=a;max+=a;}
} tree[maxn<<2];

inline void update(int rt,int w){lazy[rt]+=w;tree[rt].limit-=w;tree[rt]+=w;}

inline void pushdown(int rt){
    update(rt<<1,lazy[rt]); update(rt<<1|1,lazy[rt]);
    lazy[rt]=0;
}

接着是整块更新（注意当 limit 不为正时，要进行交替，将懒标记下传给子树，判断其是否需要交替）。

Code

inline void update(int rt,int w){lazy[rt]+=w;tree[rt].limit-=w;tree[rt]+=w;}
inline void Update(int rt,int w){
    if(w>tree[rt].limit){
        update(rt,w);
        Update(rt<<1,lazy[rt]); Update(rt<<1|1,lazy[rt]);
        tree[rt]=tree[rt<<1]+tree[rt<<1|1];
        lazy[rt]=0;
    }
    else update(rt,w);
}
inline void revise(int rt,int l,int r,int L,int R,int w){
    if(l>R||r<L) return ;
    if(l>=L&&r<=R){Update(rt,w);return ;}
    if(lazy[rt]) pushdown(rt);
    int mid=(l+r)>>1;
    revise(rt<<1,l,mid,L,R,w); revise(rt<<1|1,mid+1,r,L,R,w);
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

查询操作

类似于普通线段树的写法（要注意合并顺序先左后右）。

Code

inline node query(int rt,int l,int r,int L,int R){
    if(l>=L&&r<=R) return tree[rt];
    if(lazy[rt]) pushdown(rt);
    int mid=(l+r)>>1;
    node a; a.init();
    if(L<=mid) a=a+query(rt<<1,l,mid,L,R);
    if(R>mid) a=a+query(rt<<1|1,mid+1,r,L,R);
    return a;
}

时间复杂度

有点菜证不来，大概是 O((n+m)\log^3n)。

Code

#include<bits/stdc++.h>
#define int long long
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
const int maxn=1e6+10;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) {x=~(x-1); putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n=read(),m=read(),val[maxn],lazy[maxn];
struct line{
    int k,b;
    line operator +(const line &a){return (line){k+a.k,b+a.b};}
    void operator +=(const int &a){b+=k*a;}
    bool operator <(const line &a){return (k<a.k||(k==a.k&&b<a.b));}
};
std::pair<line,int> getmax(line n1,line n2){
    if(n1<n2) std::swap(n1,n2);
    if(n1.b>=n2.b) return std::make_pair(n1,LLONG_MAX);
    return std::make_pair(n2,(n1.b-n2.b)/(n2.k-n1.k));
}
struct node{
    line sum,lmax,rmax,max;
    int limit;
    inline void init(){
        lmax=rmax=max=sum={0,0};
        limit=LLONG_MAX;
    }
    node operator +(const node &a){
        node ans; ans.limit=std::min(limit,a.limit);
        std::pair<line,int> tmp=getmax(lmax,sum+a.lmax);
        ans.lmax=tmp.first;
        ans.limit=std::min(ans.limit,tmp.second);
        tmp=getmax(a.rmax,rmax+a.sum);
        ans.rmax=tmp.first;
        ans.limit=std::min(ans.limit,tmp.second);
        tmp=getmax(max,a.max);
        ans.limit=std::min(ans.limit,tmp.second);
        tmp=getmax(tmp.first,rmax+a.lmax);
        ans.max=tmp.first;
        ans.limit=std::min(ans.limit,tmp.second);
        ans.sum=sum+a.sum;
        return ans;

    }
    void operator +=(const int &a){sum+=a;lmax+=a;rmax+=a;max+=a;}
} tree[maxn<<2];
inline void build(int rt,int l,int r){
    if(l==r){
        line w={1,val[l]};
        tree[rt]={w,w,w,w,LLONG_MAX};
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
inline void update(int rt,int w){lazy[rt]+=w;tree[rt].limit-=w;tree[rt]+=w;}
inline void Update(int rt,int w){
    if(w>tree[rt].limit){
        update(rt,w);
        Update(rt<<1,lazy[rt]); Update(rt<<1|1,lazy[rt]);
        tree[rt]=tree[rt<<1]+tree[rt<<1|1];
        lazy[rt]=0;
    }
    else update(rt,w);
}
inline void pushdown(int rt){
    update(rt<<1,lazy[rt]); update(rt<<1|1,lazy[rt]);
    lazy[rt]=0;
}
inline void revise(int rt,int l,int r,int L,int R,int w){
    if(l>R||r<L) return ;
    if(l>=L&&r<=R){Update(rt,w);return ;}
    if(lazy[rt]) pushdown(rt);
    int mid=(l+r)>>1;
    revise(rt<<1,l,mid,L,R,w); revise(rt<<1|1,mid+1,r,L,R,w);
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
inline node query(int rt,int l,int r,int L,int R){
    if(l>=L&&r<=R) return tree[rt];
    if(lazy[rt]) pushdown(rt);
    int mid=(l+r)>>1;
    node a;    a.init();
    if(L<=mid) a=a+query(rt<<1,l,mid,L,R);
    if(R>mid) a=a+query(rt<<1|1,mid+1,r,L,R);
    return a;
}
inline void work(){
    f(i,1,n) val[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read(),l=read(),r=read(),x;
        if(opt==1) x=read(),revise(1,1,n,l,r,x);
        else write(std::max(0LL,query(1,1,n,l,r).max.b)),puts("");
    }
}
signed main(){work();return !!!!!("YZren");}

中文代码

#include<bits/stdc++.h>
#define 长整型 long long
#define 求最大值 max
#define 求最小值 min
#define 倘若 if
#define 否则 else 
#define 重载运算符 operator
#define 结构体 struct
#define 无返回值型 void
#define 布尔型 bool
#define 双返回值型 pair
#define 循环(i,j,k) for(长整型 i=j;i<=k;i++)
#define 反向循环(i,j,k) for(长整型 i=j;i>=k;i--)
#define 返回 return 
#define 常数 const
#define 声明 inline
#define 函数库 std
#define 当循环 while
#define 字符类型 char
#define 读入字符 getchar
#define 输出字符 putchar
#define 换行输出 puts
#define 主函数 main
#define 修饰整数型 signed
#define 第一个 first
#define 第二个 second
常数 长整型 最大数量=1e6+10,正无穷=1e18;
声明 长整型 读取(){
    长整型 x=0,f=1;字符类型 字符=读入字符();
    当循环(字符<'0'||字符>'9'){倘若(字符=='-')f=-1;字符=读入字符();}
    当循环(字符>='0'&&字符<='9'){x=x*10+字符-48;字符=读入字符();}
    返回 x*f;
}
声明 无返回值型 写入(长整型 x){
    倘若(x<0){x=~(x-1);输出字符('-');}
    倘若(x>9)写入(x/10);
    输出字符(x%10+'0');
}
长整型 点数=读取(),操作数=读取(),数值[最大数量],懒标记[最大数量];
结构体 线段{
    长整型 斜率,截距;
    线段 重载运算符+(常数 线段 &a){返回 {斜率+a.斜率,截距+a.截距};}
    无返回值型 重载运算符+=(常数 长整型 &a){截距+=斜率*a;}
    布尔型 重载运算符<(常数 线段 &a){返回(斜率<a.斜率||(斜率==a.斜率&&截距<a.截距));}
};
函数库::双返回值型<线段,长整型> 获取最大值(线段 线1,线段 线2){
    倘若(线1<线2)函数库::swap(线1,线2);
    倘若(线1.截距>=线2.截距)返回 函数库::make_pair(线1,正无穷);
    返回 函数库::make_pair(线2,(线1.截距-线2.截距)/(线2.斜率-线1.斜率));
}
结构体 节点{
    线段 总和,左最大,右最大,最大值;
    长整型 限制;
    声明 无返回值型 初始化(){
        左最大=右最大=最大值=总和={0,0};
        限制=正无穷;
    }
    节点 重载运算符+(常数 节点 &a){
        节点 结果;
        结果.限制=函数库::求最小值(限制,a.限制);
        函数库::双返回值型<线段,长整型> 临时=获取最大值(左最大,总和+a.左最大);
        结果.左最大=临时.第一个;
        结果.限制=函数库::求最小值(结果.限制,临时.第二个);
        临时=获取最大值(a.右最大,右最大+a.总和);
        结果.右最大=临时.第一个;
        结果.限制=函数库::求最小值(结果.限制,临时.第二个);
        临时=获取最大值(最大值,a.最大值);
        结果.限制=函数库::求最小值(结果.限制,临时.第二个);
        临时=获取最大值(临时.第一个,右最大+a.左最大);
        结果.最大值=临时.第一个;
        结果.限制=函数库::求最小值(结果.限制,临时.第二个);
        结果.总和=总和+a.总和;
        返回 结果;
    }
    无返回值型 重载运算符+=(常数 长整型 &a){
        总和+=a;
        左最大+=a;
        右最大+=a;
        最大值+=a;
    }
}线段树[最大数量<<2];
声明 无返回值型 构建(长整型 当前节点,长整型 左,长整型 右){
    倘若(左==右){
        线段 初始值={1,数值[左]};
        线段树[当前节点]={初始值,初始值,初始值,初始值,正无穷};
        返回;
    }
    长整型 中点=(左+右)>>1;
    构建(当前节点<<1,左,中点);
    构建(当前节点<<1|1,中点+1,右);
    线段树[当前节点]=线段树[当前节点<<1]+线段树[当前节点<<1|1];
}
声明 无返回值型 更新节点(长整型 当前节点,长整型 值){
    懒标记[当前节点]+=值;
    线段树[当前节点].限制-=值;
    线段树[当前节点]+=值;
}
声明 无返回值型 区间更新(长整型 当前节点,长整型 值){
    倘若(值>线段树[当前节点].限制){
        更新节点(当前节点,值);
        区间更新(当前节点<<1,懒标记[当前节点]);
        区间更新(当前节点<<1|1,懒标记[当前节点]);
        线段树[当前节点]=线段树[当前节点<<1]+线段树[当前节点<<1|1];
        懒标记[当前节点]=0;
    }
    否则 更新节点(当前节点,值);
}
声明 无返回值型 下推懒标记(长整型 当前节点){
    更新节点(当前节点<<1,懒标记[当前节点]);
    更新节点(当前节点<<1|1,懒标记[当前节点]);
    懒标记[当前节点]=0;
}
声明 无返回值型 修改区间(长整型 当前节点,长整型 左,长整型 右,长整型 目标左,长整型 目标右,长整型 值){
    倘若(左>目标右||右<目标左)返回;
    倘若(左>=目标左&&右<=目标右){
        区间更新(当前节点,值);
        返回;
    }
    倘若(懒标记[当前节点])下推懒标记(当前节点);
    长整型 中点=(左+右)>>1;
    修改区间(当前节点<<1,左,中点,目标左,目标右,值);
    修改区间(当前节点<<1|1,中点+1,右,目标左,目标右,值);
    线段树[当前节点]=线段树[当前节点<<1]+线段树[当前节点<<1|1];
}
声明 节点 查询区间(长整型 当前节点,长整型 左,长整型 右,长整型 目标左,长整型 目标右){
    倘若(左>=目标左&&右<=目标右)返回 线段树[当前节点];
    倘若(懒标记[当前节点])下推懒标记(当前节点);
    长整型 中点=(左+右)>>1;
    节点 结果;结果.初始化();
    倘若(目标左<=中点)结果=结果+查询区间(当前节点<<1,左,中点,目标左,目标右);
    倘若(目标右>中点)结果=结果+查询区间(当前节点<<1|1,中点+1,右,目标左,目标右);
    返回 结果;
}
声明 无返回值型 主程序(){
    循环(i,1,点数)数值[i]=读取();
    构建(1,1,点数);
    当循环(操作数--){
        长整型 操作类型=读取(),左=读取(),右=读取(),值;
        倘若(操作类型==1){
            值=读取();
            修改区间(1,1,点数,左,右,值);
        }
        否则{
            写入(函数库::求最大值(0LL,查询区间(1,1,点数,左,右).最大值.截距));
            换行输出("");
        }
    }
}
修饰整数型 主函数(){主程序();返回 !!!!!("YZren");}

题解：P5693 EI 的第六分块

EI 的第六分块

题目大意

解题思路

KTT 的核心思想

维护的信息

合并区间

Code

维护 limit

Code

区间更新

Code

Code

查询操作

Code

时间复杂度

Code

中文代码

维护 `limit`