自动搬运

查看原文

来自洛谷，原作者为

	Utilokasteinn 技不如人

搬运于2025-08-24 22:18:56，当前版本为作者最后更新于2020-06-26 14:10:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P6242 【模板】线段树 3

题目简介

给你一个长度为 $n$ 的序列 $a$。最开始令序列 $b=a$。

现在进行 $m$ 次操作，分为 $5$ 种：

• 1 l r k：将 $a_l\sim a_r$ 加上 $k$。

• 2 l r v：将 $a_l\sim a_r$ 对 $v$ 取最小值。

• 3 l r：求 $a_l\sim a_r$ 的和。

• 4 l r：求 $a_l\sim a_r$ 的最大值。

• 5 l r：求 $b_l\sim b_r$ 的最大值。

每次操作后令 $b_{i}=\max(b_{i},a_{i})$ 。

---

思路

前置知识：只要会写线段树 $1$。

吉司机线段树模版题，考虑用线段树维护。（大雾）

先讲一些基础的东西，会的可以直接跳到后面。

我们从线段树 $1$ 开始。线段树 $1$ 的操作就是操作 $1$ 和 $3$。

先考虑解决操作 $4$，求区间最大值。

每个节点维护一个 $\tt maxn$ 表示该节点表示的区间的最大值。

区间加时就直接把这个 $\tt maxn$ 加上 $k$。标记下传的时候也是同理。查询的时候就方便了。

现在我们解决了操作 $1,3$ 和 $4$。

接下来我们尝试解决操作 $5$。

先引入 $2$ 个概念：

• $a_i$ 的历史最（小$/$大）值：$a_{i}$ 存放过的最（小$/$大）的数。

• 区间最（小$/$大）值操作：将 $a_l\sim a_r$ 中的数 $a_{i}$ 变为 $\min(a_i,v)$ 或 $\max(a_i,v)$。

显然在这题中，$b_i$ 就是 $a_i$ 的历史最大值，操作 $2$ 就是区间最小值操作，操作 $5$ 是求区间最大历史最大值。

看完上面的定义后，再来尝试解决一下。

操作 $5$ 的瓶颈在于区间加后无法快速更新序列 $b$。

因为一个区间总能被若干个点表示，我们先将一个区间先简化一个节点。

我们在区间加时，会对一个区间加上 $k$。

若 $k>0$，历史最大值可能被更新。

在 $k=0$，相当于什么也没做。

若 $k<0$，历史最大值不可能被更新。

想象一下我们正在对一个节点（不是任意区间）进行疯狂的区间加，此时也就是该节点的 $\tt tag$ 在一直被改变。

经过一次加法，这个 $\tt tag$ 可能变大（$k>0$），也可能变小（$k<0$）。

但是我们注意到，那么在标记下传前，当前节点的儿子的值是不会变的。

那么显然，当 $\tt tag$ 达到最大时，下传的时候才可以使儿子达到当前最大。而只有当前最大才有可能更新历史最大。

假设这个这个 $\tt tag$ 为 $\tt tag1$。

那么，我们只需要再设一个 $\tt tag2$ 来表示没下传前的最大 $\tt tag1$，那么下传更新序列 $b$ 就容易了。

注意下传时的顺序，要先更新 $\tt maxb$ 再更新 $\tt maxa$，先更新 $\tt tag2$ 再更新 $\tt tag1$。

可以过测试点 $5$ 和 $6$ 的代码，再往下就是完整的代码。

这里一定要理解透，不然后面肯定都看不懂。

---

接下来进入正题，如何解决操作 $2$。

容易发现这道题的瓶颈在于进行操作 $2$ 后，无法快速更新信息，不仅区间历史最大值更新不了，甚至连区间和都不好更新。只能递归到叶子节点，然后对其取最小值，然后返回。

这样写单次修改的时间复杂度就会达到惊人的 $\mathcal{O}(n)$。

那怎么办呢？

线段树显然不能直接区间取 $\min$。

我们可以换一个思路，可以把区间内大于 $v$ 的数都减去一个数，使得这些数都变为 $v$。

因为不同的数要减去不同的数才能等于 $v$，显然我们不能设很多 $\tt tag$ 来表示区间内不同的数要减去的数。

那退一步来讲，若区间内大于 $v$ 的数只有一种，我们可以怎么做呢？

只需要维护一个 $\tt tag$ 就行了。

那怎样才能使得区间内大于 $v$ 的数只有一种呢？

只需要多递归几次就行了。

我们在线段树每个节点设以下 $3$ 个变量，分别为：

• $\tt maxn$：该区间的最大值。

• $\tt se$：该区间的严格次大值，也就是最大的比最大值小的值。

• $\tt cnt$：该区间的最大值的个数。

因为只有在区间只有一种数大于 $k$ 的时候我们才能快速更新，即只能在满足 $\tt se$ $<k<$ $\tt maxn$ 的节点上更新。

综上所述，解决方法就是在线段树中递归，直到该区间大于 $v$ 的数只有一种就更新。

这样做总的时间复杂度为 $\mathcal{O}(m\log^2n)$，但我不会证。

因为有人说只需要设 $3$ 个 $\tt tag$，这显然是不行的吧。所以再来说明一下为什么需要设 $4$ 个 $\tt tag$。

在没有操作 $2$ 的情况下，我们就设了 $2$ 个 $\tt tag$，来维护整个区间。

现在加入了区间取 $\min$ 操作。而区间取 $\min$ 操作只会更新区间最大值。

那么我们就需要把最大值和非最大值分开来维护，故要设 $4$ 个 $\tt tag$。

换句话说，如果不设 $4$ 个 $\tt tag$，就更新不了非最大历史最大值的历史最大值了。

---

代码及其理解

首先说明，本题解主要以代码为主。个人认为代码写得很清晰，如果懂得上述思路就一定可以看懂。

先来看一下线段树每个节点需要存些什么。

以下是需要维护的 $\tt tag$：

• $\tt add1$：该区间最大值的懒标记。

• $\tt add2$：该区间非最大值的懒标记。

• $\tt add3$：该区间最大值的懒标记的最大值。

• $\tt add4$：该区间非最大的值的懒标记的最大值。

具体地，$\tt add3$ 是在未下传懒标记前最大的 $\tt add1$ 的值，$\tt add4$ 是在未下传懒标记前最大的 $\tt add2$ 的值。

这 $4$ 个 $\tt tag$ 只要理解透了，代码就一定可以看得懂。

其他就简单了，具体详见代码。

这里需要注意，一个区间可能只有一种数，这样就没有区间严格次大值。这时我们需要给 $\tt se$ 赋一个极小值。

建树代码如下：

struct segment_tree{
	ll sum;
	int l,r,maxa,cnt,se,maxb;
	int add1,add2,add3,add4;
}s[2000005];
inline void push_up(int p)
{
	s[p].sum=s[p*2].sum+s[p*2+1].sum;
	s[p].maxa=max(s[p*2].maxa,s[p*2+1].maxa);
	s[p].maxb=max(s[p*2].maxb,s[p*2+1].maxb);
	if(s[p*2].maxa==s[p*2+1].maxa)
	{
		s[p].se=max(s[p*2].se,s[p*2+1].se);
		s[p].cnt=s[p*2].cnt+s[p*2+1].cnt;
	}
	else if(s[p*2].maxa>s[p*2+1].maxa)
	{
		s[p].se=max(s[p*2].se,s[p*2+1].maxa);
		s[p].cnt=s[p*2].cnt;
	}
	else
	{
		s[p].se=max(s[p*2].maxa,s[p*2+1].se);
		s[p].cnt=s[p*2+1].cnt;
	}
}
void build(int l,int r,int p)
{
	s[p].l=l,s[p].r=r;
	if(l==r)
	{
		s[p].sum=s[p].maxa=s[p].maxb=read();
		s[p].cnt=1,s[p].se=-2e9;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	push_up(p);
}

---

查询与普通的线段树无异，注意求和要开 long long。

代码如下：

ll query_sum(int p)
{
	if(l>s[p].r||r<s[p].l)return 0;
	if(l<=s[p].l&&s[p].r<=r)return s[p].sum;
	push_down(p);
	return query_sum(p*2)+query_sum(p*2+1);
}
int query_maxa(int p)
{
	if(l>s[p].r||r<s[p].l)return -2e9;
	if(l<=s[p].l&&s[p].r<=r)return s[p].maxa;
	push_down(p);
	return max(query_maxa(p*2),query_maxa(p*2+1));
}
int query_maxb(int p)
{
	if(l>s[p].r||r<s[p].l)return -2e9;
	if(l<=s[p].l&&s[p].r<=r)return s[p].maxb;
	push_down(p);
	return max(query_maxb(p*2),query_maxb(p*2+1));
}

---

我们先来看一下修改时要如何维护 $\tt tag$ 以及其信息。

先是区间加修改的代码：

void update_add(int p)
{
	if(l>s[p].r||r<s[p].l)return;
	if(l<=s[p].l&&s[p].r<=r)
	{
		s[p].sum+=1ll*k*s[p].cnt+1ll*k*(s[p].r-s[p].l+1-s[p].cnt);
		s[p].maxa+=k;
		s[p].maxb=max(s[p].maxb,s[p].maxa);
		if(s[p].se!=-2e9)s[p].se+=k;
		s[p].add1+=k,s[p].add2+=k;
		s[p].add3=max(s[p].add3,s[p].add1);
		s[p].add4=max(s[p].add4,s[p].add2);
		return;
	}
	push_down(p);
	update_add(p*2),update_add(p*2+1);
	push_up(p);
}

根据 $\tt tag$ 的定义，不难写出以上代码。

就是不管最大值还是非最大值，都加上 $k$，维护一下区间和。

然后 $\tt tag$ 也不需要管是否为最大值，都加上 $k$。

最后记录一下未下传前最大的 $\tt tag$ 的值是多少。

接着就是区间取 $\min$ 的代码：

void update_min(int p)
{
	if(l>s[p].r||r<s[p].l||v>=s[p].maxa)return;
	if(l<=s[p].l&&s[p].r<=r&&s[p].se<v)
	{
		int k=s[p].maxa-v;
		s[p].sum-=1ll*s[p].cnt*k;
		s[p].maxa=v,s[p].add1-=k;
		return;
	}
	push_down(p);
	update_min(p*2),update_min(p*2+1);
	push_up(p);
}

代码做的事大致就是，先递归到一个满足 $\tt se$ $<v<$ $\tt maxa$ 的节点，然后将区间最大值都变为 $v$，更新区间和，区间最大值以及 $\tt tag$。

因为只修改最大值，所以只用更新 $\tt add1$。因为是取 $\min$，所以肯定不会更新历史最大值。

---

最后来看一下本题的难点，push_down 是如何下传懒标记。

先放上代码：

inline void change(int k1,int k2,int k3,int k4,int p)
{
	s[p].sum+=1ll*k1*s[p].cnt+1ll*k2*(s[p].r-s[p].l+1-s[p].cnt);
	s[p].maxb=max(s[p].maxb,s[p].maxa+k3);
	s[p].maxa+=k1;
	if(s[p].se!=-2e9)s[p].se+=k2;
	s[p].add3=max(s[p].add3,s[p].add1+k3);
	s[p].add4=max(s[p].add4,s[p].add2+k4);
	s[p].add1+=k1,s[p].add2+=k2;
}
inline void push_down(int p)
{
	int maxn=max(s[p*2].maxa,s[p*2+1].maxa);
	if(s[p*2].maxa==maxn)
	    change(s[p].add1,s[p].add2,s[p].add3,s[p].add4,p*2);
	else change(s[p].add2,s[p].add2,s[p].add4,s[p].add4,p*2);
	if(s[p*2+1].maxa==maxn)
		change(s[p].add1,s[p].add2,s[p].add3,s[p].add4,p*2+1);
	else change(s[p].add2,s[p].add2,s[p].add4,s[p].add4,p*2+1);
	s[p].add1=s[p].add2=s[p].add3=s[p].add4=0;
}

看着就很恶心，但其实也不难。

push_down 中是判断该区间的最大值是否位于左区间或右区间，是就下传最大值的 $\tt tag$，否则就下传非最大值的 $\tt tag$。

change 就是下传 $\tt tag$ 以及更新儿子的信息。根据各个 $\tt tag$ 的定义都不难写出。

注意下传的顺序。

最后记得清空 $\tt tag$。

如果看不懂，就把测试点 $5$ 和 $6$ 的代码理解透彻了再来看。

---

注意事项&常数优化

1. 使用快读和快写。

2. 求和开 long long。

3. 只有求和才开 long long，其他用 int。这样可以比全用 long long 快半秒左右。

4. 递归的时候参数尽量少。

5. 用一个结构体来储存树的各种信息，这样空间访问较连续，速度较快。

6. 在建树的时候读入，可以一定的节省空间和时间。

7. 加一些函数前加 inline。

8. 修改时的更新可以用 change 代替，可以减少大量码量。

9. 注意更新顺序。

---

其他

最后附上 AC Code，在第一篇代码的下面。

参考资料：

• 灵梦の题解。

• 灵梦の洛谷日报。

• OI-Wiki。

$\tt Updated\;on\;10.3,2020$：整篇重写。

$\tt Updated\;on\;7.31,2021$：补充了之前少写的 update_add。大面积修改，删减。

$\tt Updated\;on\;4.17,2022$：几乎整篇重写。

$\tt Updated\;on\;8.14,2022$：修改了一些小错误。重写了半篇，减少了文字量，更新了代码。

$\tt Updated\;on\;1.8,2023$：删改了小部分内容，添加了部分内容，添加了测试点 $5$ 和 $6$ 的代码，解释了为什么要设 $4$ 个 $\tt tag$ 来维护。