专栏文章

题解：P5693 EI 的第六分块

YYZren
P5693题解参与者 6已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mip17jqq
此快照首次捕获于
2025/12/03 04:29
3 个月前
此快照最后确认于
2025/12/03 04:29
3 个月前
查看原文

EI 的第六分块

题目大意

给定一个长度为 nn 的整数序列，支持两种操作：
  1. 区间加一个正数
  2. 查询区间最大子段和（可以为空）

解题思路

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

KTT 的核心思想

KTT 维护的每个节点包含一个一次函数 y=k×val+by = k \times val + b，其中：
  • kk 是斜率
  • bb 是截距
  • valval 是当前节点的值
每次区间加操作相当于对 bb 进行修改：b=b+k×valb = b + k \times val。

维护的信息

每个节点需要维护以下信息：
  1. sum：区间和
  2. lmax：从左端点开始的最大子段和
  3. rmax：从右端点开始的最大子段和
  4. max：区间最大子段和
  5. limit：一个阈值，用于判断何时需要更新最大值

合并区间

合并两个子区间时，需要注意顺序，并正确计算各个值：
  1. lmax：取左子区间的 lmax 或左子区间的 sum 加上右子区间的 lmax 中的较大值
  2. rmax：取右子区间的 rmax 或右子区间的 sum 加上左子区间的 rmax 中的较大值
  3. max：取左子区间的 max、右子区间的 max 或左子区间的 rmax 加上右子区间的 lmax 中的最大值
  4. sum：左右子区间 sum 的和

Code

CPP
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。
  1. 第一种情况（交点是正数，所以 limit 可以更新）。
  2. 第二种情况（两条直线平行没有交点（交点是负数也一样），返回正无穷让其不更新）。
取这个交点就很简单了（注意还要返回先交替的直线，也就是下面那一条）。

Code

CPP
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));
}

区间更新

和普通的线段树的过程差不多。
  1. 先看标记下传的实现。

Code

CPP
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;
}
  1. 接着是整块更新（注意当 limit 不为正时，要进行交替，将懒标记下传给子树，判断其是否需要交替）。

Code

CPP
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

CPP
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)O((n+m)\log^3n)。

Code

CPP
#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");}

中文代码

CPP
#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");}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...