Luogu EI 的第六分块 // KTT 学习记录

P5693 EI 的第六分块

题目描述

给定一个整数序列，支持区间加正整数以及查询区间最大子段和。

思路

使用线段树记录四个信息来维护答案：

• \(sum_i\)：区间和；
• \(lmax_i\)：最大前缀和；
• \(rmax_i\)：最大后缀和；
• \(mx_i\)：最大子段和。

合并时我们分类讨论：

• \(lmax = \max(lmax_{ls},sum_{ls}+lmax_{rs})\)；
• \(rmax = \max(rmax_{rs},sum_{rs}+rmax_{ls})\)；
• \(mx = \max(mx_{ls},mx_{rs},rmax_{ls}+lmax_{rs})\)。

KTT 部分

我推荐直接去看集训队论文或者一些大佬的讲解。复杂度我不会证，请看 EI 队长的证明。
（KTT 我没学会严谨说明，只能全靠感性理解了。）

显然我们需要维护 \(lmax_i\)、\(rmax_i\)、\(mx_i\)、\(sum_i\) 的最大值，所以我们把需要维护的每一个信息都看作一条一次函数，现在问题变成了一次函数比大小。
我们在九年义务教育中学习一次函数时，老师教导我们要看函数的交点数形结合来求不等式解集。

Push_down/Push_up

所以我们现在额外维护一个阈值 \(dx\) 记录区间最大值何时在函数间进行交换（可以看作是两条一次函数的交点相对于区间的位置）。当 \(dx<0\) 时，代表此时区间的最大值应该在函数之间进行交换了（解集对函数的选取以交点相对于区间的位置为分界）。

区间加 \(k_i\) 看作是函数向上移动，此时我们令 \(dx\gets dx-k_i\)（可以看作是函数交点进行了左右移动）。向上维护时，我们还需要对 \(dx\) 进行更新。我们要找到最小的阈值，当然为 \(\min(dx_{ls},dx_{rs},dx\in\{x\mid f_1(x)=f_2(x)\})\)。

Rebuild

我们在 Update 后，可能会导致节点子树内的 \(dx\) 发生变化，而当 \(dx<0\) 时会导致最大值选取发生变化。
所以我们在做更新后需要对节点子树 Rebuild，二次递推来更新 \(dx\)。

Update/Query

正常进行修改和查询即可，记得 Rebuild。
（注：请注意左右区间的合并顺序对答案产生的影响。）

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){//快读
	int w=0;x=0;
	char ch = getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
template <typename T>
inline T Min(T x,T y){ return (x < y ? x : y); }
const int N = 4e5+10;
const ll INF = 1e16;
struct Func{//一次函数
	ll k,b;
	Func(){
		k = 0; b = 0;
	}
	Func(ll tk,ll tb){
		k = tk; b = tb;
	}
	inline Func operator + (const Func&G) const{//函数合并
		return Func(k+G.k,b+G.b);
	}
	inline bool operator < (const Func&G) const{//两个函数有没有交点
		return k==G.k && b<G.b || k<G.k;
	}
	inline ll operator & (const Func&G) const{//求交点
		return (G.b-b)/(k-G.k);
	}
	inline void operator += (const ll&G){//函数向上移动
		b += k*G;
	}
};
struct Tree{
	Func lx,rx,sum,mx; ll dx;//维护区间的四个信息以及阈值
	Tree(){
		dx = INF;//初始化为无穷大值，表示永远不会对最大值产生影响
	}
	Tree(Func tlx,Func trx,Func tsum,Func tmx,ll tdx){
		lx = tlx; rx = trx; sum = tsum; mx = tmx; dx = tdx;
	}
	inline void Merge_lx(Func x,Func y,Tree &tmp) const{//求lmax
		if(x<y) swap(x,y);
		if(x.b>=y.b) tmp.lx = x;
		else tmp.lx = y,tmp.dx = Min(tmp.dx,x&y);
	}
	inline void Merge_rx(Func x,Func y,Tree &tmp) const{//求rmax
		if(x<y) swap(x,y);
		if(x.b>=y.b) tmp.rx = x;
		else tmp.rx = y,tmp.dx = Min(tmp.dx,x&y);
	}
	inline void Merge_mx(Func x,Func y,Tree &tmp) const{//求mx
		if(x<y) swap(x,y);
		if(x.b>=y.b) tmp.mx = x;
		else tmp.mx = y,tmp.dx = Min(tmp.dx,x&y);
	}
	inline Tree operator + (const Tree&G) const{//区间合并
		Tree tmp; tmp.dx = Min(dx,G.dx); tmp.sum = sum+G.sum;
		Merge_lx(lx,sum+G.lx,tmp);Merge_rx(G.rx,G.sum+rx,tmp);
		Merge_mx(G.mx,mx,tmp);Merge_mx(tmp.mx,rx+G.lx,tmp);
		return tmp;
	}
	inline void operator += (const ll&G){//区间加
		lx += G; rx += G; mx += G; sum += G; dx -= G;
	}
}tr[N*3];
//题目说注意卡常，所以直接用zkw
//然后最优解了（雾）
int P=1,DEP=0,st[N*3]; ll tag[N*3];
inline void push_down(int p){//正常push_down
	if(tag[p]){
		tag[p<<1] += tag[p]; tr[p<<1] += tag[p];
		tag[p<<1|1] += tag[p]; tr[p<<1|1] += tag[p];
		tag[p] = 0;
	}
}
inline void rebuild(int p){
	if(tr[p].dx>=0) return ;
	int head = 1,tail = 0;
	st[++tail] = p; push_down(p);
	while(tail>=head){
		int ttail = tail;
		for(int j=tail,pos;j>=head;--j){
			pos = st[j]; //看子节点的子树是否需要更新
			if(tr[pos<<1].dx<0) st[++tail]=pos<<1,push_down(pos<<1);
			if(tr[pos<<1|1].dx<0) st[++tail]=pos<<1|1,push_down(pos<<1|1);
		}
		head = ttail+1;
	}//重新维护
	do{ tr[st[tail]]=tr[st[tail]<<1]+tr[st[tail]<<1|1]; } while(--tail); 
}
inline void update(int l,int r,ll k){
	l += P-1; r += P+1;//先push_down
	for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
	while(l^1^r){
		if(~l&1) tag[l^1]+=k,tr[l^1]+=k,rebuild(l^1);//别忘了rebuild
		if(r&1) tag[r^1]+=k,tr[r^1]+=k,rebuild(r^1);
		l>>=1;r>>=1;
		tr[l] = tr[l<<1]+tr[l<<1|1];
		tr[r] = tr[r<<1]+tr[r<<1|1];
	}
	for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
}
inline ll query(int l,int r){
	l += P-1; r += P+1;//先push_down
	for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
	Tree resl,resr;
	while(l^1^r){
        //注意左右区间的合并顺序
		if(~l&1) resl = resl+tr[l^1];
		if(r&1) resr = tr[r^1]+resr;
		l>>=1;r>>=1;
	}
	return (resl+resr).mx.b;
}
int main(){
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	int n,m;read(n,m);
	while(P<=n+1) P<<=1,++DEP;
	for(int i=1,k;i<=n;++i){
		read(k); Func res = Func(1ll,1ll*k);
		tr[i+P] = Tree(res,res,res,res,INF);//初始时都是y=x+a[i]
	}
	for(int i=P-1;i;--i) tr[i] = tr[i<<1]+tr[i<<1|1];
	for(int i=1,opt,l,r;i<=m;++i){
		read(opt,l,r); ll k;
		if(opt==1) read(k),update(l,r,k);
		else printf("%lld\n",(k=query(l,r))<0?0ll:k);//区间可以不选
	}
// 	fclose(stdin);
// 	fclose(stdout);
	return 0;
}

我的第一篇黑题，感谢 NianFeng 提供的帮助。