专栏文章

题解：P5693 EI 的第六分块

FFire__Fly
P5693题解参与者 5已保存评论 5

文章操作

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

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

原题传送门

思路

前置芝士：

KTT（附 2020 年国家集训队论文）

KTT 是李白天在 2020 年国家集训队论文写的一篇文章中的部分内容，文章名称为《浅谈函数最值的动态维护》，以下内容为我在学习 KTT 中的一些理解，若有误请指出。
首先我们可知用线段树求最大子段和需要维护最大前缀和 lmaxlmax，最大后缀和 rmaxrmax，最大子段和 maxnmaxn 和区间和 sumsum 四个变量。
公式为（用 ll 表示左儿子，rr 表示右儿子）：
CPP
sum=l.sum+r.sum
lmax=max(l.lmax,l.sum+r.lmax)
rmax=max(r.rmax,r.sum+l.rmax)
maxn=max(l.maxn,r.maxn,l.rmax+r.lmax)
首先如果最长子段和的区间不变，那么最长字段和每次更新就会增加区间长乘上 xx，但是由于区间里会有负数，在增加到某一时刻时会变为正数，增大区间长，所以此时线段树的每个节点存的就不再是值而是一个一次函数 y=k×x+by=k \times x+b 其中 kk 为斜率，xx 就是加的 xx，bb 就是初始值，在代码中我们只需记 kk 和 yy 就行。
然后我们需要引入 KTT 中最重要的变量：intrintr 交替阈值。
画一个图理解一下：
其中红线与蓝线汇交与一点，也就是 intrintr。当 xx 大于 intrintr 时最大值位于蓝线，否则为红线。
当然也会出现这种情况：
此时红线与蓝线并无交点，可将 intrintr 设为正无穷，表示永不会交替。
现在我们来讨论如何维护 intrintr，因为我们要维护四个参数，所以 intrintr 要取四种更新的最小值，如果 intrintr 的值小于零后就表明有至少一个值需要进行更新，所以我们可以很轻松得出这份代码：
CPP
        node c;
		pair<line , int> tmp;
		c.intr = min(a.intr , b.intr);
		tmp = maxx(a.lmax , a.sum + b.lmax);
		c.lmax = tmp.first;
		c.intr = min(c.intr , tmp.second);
		tmp = maxx(b.rmax , b.sum + a.rmax);
		c.rmax = tmp.first;
		c.intr = min(c.intr , tmp.second);
		tmp = maxx(a.maxn , b.maxn);
		c.intr = min(c.intr , tmp.second);
		tmp = maxx(a.rmax + b.lmax , tmp.first);
		c.maxn = tmp.first;
		c.intr = min(c.intr , tmp.second);
		c.sum = a.sum + b.sum;
		return c;
其中 cc 为父节点，aa 为左儿子，bb 为右儿子，maxxmaxx 为求当前最大值所在直线和交点，这样我们就可从儿子推出父亲（注意：这段代码我们可以写在重载运算符中来简化代码）。
然后我们来考虑更新，因为横坐标加 xx 就相当于 intrintr 减去 xx，所以我们在 addadd 函数中就直接将 intrintr 减去即可，如果此时 intrintr 小于零，就意味着有更优的值，我们只需向下递归，找到第一个 intrintr 大于等于零的子节点即可，然后向上 upup 即可，这个操作我们可称之为 rebuildrebuild。
以下是 addadd 和 rebuildrebuild 的代码：
CPP
	inline void push(int id , int val) {
		lazy[id] += val;
		tr[id].intr -= val;
		tr[id].lmax.b += tr[id].lmax.a * val;
		tr[id].rmax.b += tr[id].rmax.a * val;
		tr[id].maxn.b += tr[id].maxn.a * val;
		tr[id].sum.b += tr[id].sum.a * val;
		return ;
	}


	inline void add(int id , int l , int r , int ql , int qr , int val) {
		if(l >= ql && r <= qr) {
			push(id , val);
			rebuild(id);
			return ;
		}
		down(id);
		int mid = (l + r) >> 1;
		if(ql <= mid) add(id << 1 , l , mid , ql , qr , val);
		if(qr > mid) add(id << 1 | 1 , mid + 1 , r , ql , qr , val);
		up(id);
		return ;
	}


	inline void rebuild(int id) {
		if(tr[id].intr >= 0) return ;
		down(id);
		rebuild(id << 1);
		rebuild(id << 1 | 1);
		up(id);
		return ;
	}
（为了图方便，把 pushpush 函数单独拎了出来，这样可以给其他函数共同使用。）
接着是 buildbuild 函数，注意子节点的 intrintr 为正无穷，因为就一条线，没有其他的线与它竞争，故没有交替点。
buildbuild 函数：
CPP
	inline void build(int id , int l , int r) {
		lazy[id] = 0;
		if(l == r) {
			tr[id].lmax = tr[id].rmax = tr[id].maxn = tr[id].sum = {1 , aa[l]};
			tr[id].intr = inf;
			return ;
		}
		int mid = (l + r) >> 1;
		build(id << 1 , l , mid);
		build(id << 1 | 1 , mid + 1 , r);
		up(id);
		return ;
	}
最后还剩下一个 queryquery 查询函数了，与普通的线段树差不多，记得多 upup 和 downdown。
queryquery 函数：
CPP
	inline node query(int id , int l , int r , int ql , int qr) {
		if(l >= ql && r <= qr) return tr[id];
		down(id);
		int mid = (l + r) >> 1;
		node ans;
		ans.init();
		if(ql <= mid) ans = ans + query(id << 1 , l , mid , ql , qr);
		if(qr > mid) ans = ans + query(id << 1 | 1 , mid + 1 , r , ql , qr);
		return ans;
	}
至于时间复杂度，极限是 O((n+m)log⁡3n)O((n+m)\log^3n)，但一般达不到，大家当成 O((n+m)log⁡2n)O((n+m)\log^2n)，最后就是大家喜闻乐见的全部代码了，如果还有不懂的可以翻阅一下代码。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f7f7f7f7f
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
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');
}
inline void writeh(int x) {
	write(x);
	putchar('\n');
}
inline void writek(int x) {
	write(x);
	putchar(' ');
}
int n , q , aa[maxn] , opt;
struct line {
	int a , b;//a为斜率，b为y=kx+b中的y
	friend line operator +(line a1 , line b1) {
		return {a1.a + b1.a , a1.b + b1.b};
	}
};
inline pair<line , int> maxx(line a , line b) {
	if(a.a < b.a || (a.a == b.a && a.b < b.b)) swap(a , b);
	if(a.b >= b.b) return make_pair(a , inf);
	return make_pair(b , (b.b - a.b) / (a.a - b.a));
}//取更大的直线
struct node {
	line lmax , rmax , maxn , sum;
	int intr;
	void init() {
		lmax = rmax = maxn = sum = {0 , 0};
		intr = inf;
	}
	friend node operator +(node a , node b) {
		node c;
		pair<line , int> tmp;
		c.intr = min(a.intr , b.intr);
		tmp = maxx(a.lmax , a.sum + b.lmax);
		c.lmax = tmp.first;
		c.intr = min(c.intr , tmp.second);
		tmp = maxx(b.rmax , b.sum + a.rmax);
		c.rmax = tmp.first;
		c.intr = min(c.intr , tmp.second);
		tmp = maxx(a.maxn , b.maxn);
		c.intr = min(c.intr , tmp.second);
		tmp = maxx(a.rmax + b.lmax , tmp.first);
		c.maxn = tmp.first;
		c.intr = min(c.intr , tmp.second);
		c.sum = a.sum + b.sum;
		return c;
	}
};
struct KTT {
	node tr[maxn << 2];
	int lazy[maxn << 2];
	inline void up(int id) {
		tr[id] = tr[id << 1] + tr[id << 1 | 1];
		return ;
	}
	inline void push(int id , int val) {
		lazy[id] += val;
		tr[id].intr -= val;
		tr[id].lmax.b += tr[id].lmax.a * val;
		tr[id].rmax.b += tr[id].rmax.a * val;
		tr[id].maxn.b += tr[id].maxn.a * val;
		tr[id].sum.b += tr[id].sum.a * val;
		return ;
	}
	inline void down(int id) {
		if(lazy[id]) {
			push(id << 1 , lazy[id]);
			push(id << 1 | 1 , lazy[id]);
			lazy[id] = 0;
		}
		return ;
	}
	inline void build(int id , int l , int r) {
		lazy[id] = 0;
		if(l == r) {
			tr[id].lmax = tr[id].rmax = tr[id].maxn = tr[id].sum = {1 , aa[l]};
			tr[id].intr = inf;
			return ;
		}
		int mid = (l + r) >> 1;
		build(id << 1 , l , mid);
		build(id << 1 | 1 , mid + 1 , r);
		up(id);
		return ;
	}
	inline void rebuild(int id) {
		if(tr[id].intr >= 0) return ;
		down(id);
		rebuild(id << 1);
		rebuild(id << 1 | 1);
		up(id);
		return ;
	}
	inline void add(int id , int l , int r , int ql , int qr , int val) {
		if(l >= ql && r <= qr) {
			push(id , val);
			rebuild(id);
			return ;
		}
		down(id);
		int mid = (l + r) >> 1;
		if(ql <= mid) add(id << 1 , l , mid , ql , qr , val);
		if(qr > mid) add(id << 1 | 1 , mid + 1 , r , ql , qr , val);
		up(id);
		return ;
	}
	inline node query(int id , int l , int r , int ql , int qr) {
		if(l >= ql && r <= qr) return tr[id];
		down(id);
		int mid = (l + r) >> 1;
		node ans;
		ans.init();
		if(ql <= mid) ans = ans + query(id << 1 , l , mid , ql , qr);
		if(qr > mid) ans = ans + query(id << 1 | 1 , mid + 1 , r , ql , qr);
		return ans;
	}
}tree;
signed main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) aa[i] = read();
	tree.build(1 , 1 , n);
	int l , r , x;
	for(int i = 1; i <= q; i++) {
		cin >> opt >> l >> r;
		if(opt == 1) {
			cin >> x;
			tree.add(1 , 1 , n , l , r , x);
		}else writeh(max(0ll , tree.query(1 , 1 , n , l , r).maxn.b));
	}
	return !("wjl1100 qwq");
}

小结：

不知不觉已经写了这么多了，顺便提一句，我竟是这道题的第 1000 次通过。

评论

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

正在加载评论...