# P7476 「C.E.L.U-02」苦涩 ## 题目背景回想起自己的过往的人生，YQH 觉...

Question

P7476 「C.E.L.U-02」苦涩

题目背景

回想起自己的过往的人生，YQH 觉得心中充满了苦涩。如果人生能再来一次，我一定会少做一些傻事，少真香几次，然后大胆地去追寻自己的爱。可惜没有这样一个机会了。

题目描述

在 YQH 的梦中，他看到自己过去的记忆正在不断浮现在自己脑中。这些记忆带给他的是满满的苦涩。他想要强行忘记一些来减轻自己的苦涩。
YQH 的脑中可以被分成 $n$ 个片区，每个片区相当于一个存放记忆的可重集，初始为空。他将进行 $m$ 次这三种操作：
操作 1：区间 $l\sim r$ 的片区中都浮现了一个苦涩值为 $k$ 的记忆。
操作 2：YQH 开始清理 $l\sim r$ 片区的记忆。如果一个片区 $k\in[l,r]$ 且 $k$ 中苦涩值最大的记忆与 $l\sim r$ 片区中苦涩值最大的记忆相等，则将这个苦涩值最大的记忆忘记。如果在同一个片区有多个相同的苦涩值最大的记忆，则只忘记一个。如果这些片区内没有记忆，则无视。
操作 3：YQH 想知道， $l\sim r$ 片区中苦涩值最大的记忆的苦涩值是多少，如果不存在，输出-1。

输入格式

第一行两个数， $n,m$ 。
接下来 $m$ 行，第一个数代表操作种类 $op$ ，对于操作 1，有三个数 $l,r,k$ ，对于操作 2 或 3，有两个数 $l,r$ 。

输出格式

对于每个操作 3 输出一行，代表答案。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

text
2
2

说明/提示

样例解释

样例解释一

下面为各操作之后 YQH 的大脑的状态：
第一次操作： $\{2\},\{2\},\{2\},\varnothing,\varnothing$
第二次操作： $\{2\},\{2,3\},\{2,3\},\{3\},\varnothing$
第三次操作： $\{2\},\{2,3\},\{2\},\{3\},\varnothing$
第四次操作询问区间 $1\sim 3$ 的最大值，所以答案是 $3$ 。

样例解释二

下面为各操作之后 YQH 的大脑的状态：
第一次操作： $\{2\},\{2\},\{2\},\{2\},\{2\},\{2\}$
第二次操作： $\{2\},\{2\},\{2,2\},\{2\},\{2\},\{2\}$
第三次操作： $\{2\},\{2\},\{2,2,3\},\{2,3\},\{2\},\{2\}$
第四次操作： $\{2\},\{2\},\{2,2\},\{2\},\{2\},\{2\}$
第五次操作询问 $3$ 的最大值，所以答案是 $2$ 。
第六次操作询问 $4$ 的最大值，所以答案是 $2$ 。

数据范围

Subtask	n	m	特殊性质
$1(10pts)$	$\leq10^3$	$\le10^3$	$\diagdown$
$2(20pts)$	$\leq5\times10^4$	$\leq5\times10^4$	没有操作 2
$3(10pts)$	$\leq5\times10^4$	$\leq5\times10^4$	操作 2 中 $l=r$
$4(20pts)$	$\leq5\times10^4$	$\leq5\times10^4$	$\diagdown$
$5(20pts)$	$\leq2\times10^5$	$\leq2\times10^5$	操作 2 中 $l=r$
$6(20pts)$	$\leq2\times10^5$	$\leq2\times10^5$	$\diagdown$

对于 $100\%$ 的数据， $n,m\le2\times10^5,k\le10^9$

闲话：众所周知校内模拟赛很喜欢搬题，于是我们的 @CYJian 就放了 T1 签，T2 难，T3 签，T4 中，T5 签，然后这个蒟蒻只会 T5。而且还想了 $1.5h$ 。然后 T1 的贪心以为是假的所以就去梭哈最难的 T2 了。最终分数显然易得。

根据我们的 d** 同学所使用的方法——观察数据范围推测算法时空复杂度，然后由于 T1 数据范围 $1.5\times 10^5$ ，以为要上数据结构，最后写了 $4.69KB$ 、 $244$ 行的代码，拿了 $0pts$ ，于是被老师喷了：那我开 $1GB$ 你是不是还要考虑可持久化一下。

解题思路

你猜用什么算法喵

以下讨论时间复杂度中的 $n$ 并不代表题目中的 $n$ 。

但是这道题目用以上方法就不难瞅出大概是 $\mathcal{O}(n \log n)$ 、 $\mathcal{O}(n \log^2 n)$ 或者 $\mathcal{O}(n \sqrt{n})$ 的算法。当然，如果你像某位卡常代师可以把 $8e9$ 的复杂度卡到 $5e8$ 的话，可以考虑考虑 $\log^3$ 做法。

但是一眼 $\mathcal{O}(n \log n)$ 的算法大概率是没有的，毕竟你区间操作带只 $\mathcal{O}(\log)$ ，而且删除操作一看就很难 $\mathcal{O}(\log)$ 删完。如果您可以 $\mathcal{O}(n \log n)$ 过掉可以告诉我，让我膜拜 ds 大神啊。

所以考虑 $\mathcal{O}(n \sqrt{n})$ 的算法。区间操作很容易想到分块或者莫队，但是区间 $[l, r)$ 跟区间 $[l, r]$ 似乎没有什么联系，所以只能考虑分块，但是显然每个块至少需要排序吧。所以复杂度为 $\mathcal{O}(n \sqrt{n} \log n)$ ，大概率过不了了。

最后只剩下 $\mathcal{O}(n \log^2 n)$ 的算法（ $\mathcal{O}(n)$ 算法一眼不可做）。

看到区间操作首先想差分、数据结构、分块、莫队对吧，但是差分肯定不行，分块之前说明过时间复杂度有问题，莫队正确性有问题。所以只剩下数据结构。那我们再列举一下数据结构：线段树、树状数组、平衡树……剩下的应该没用吧。平衡树支持插入、删除操作，但是区间插入、删除似乎还是有点困难。树状数组看着不太行的样子。酱紫就只剩下线段树了。

WTF，XX线段树怎么维护呢？当然肯定是求助「神」啦。「神」告诉你可以使用线段树套堆，于是你恍然大悟。但是你并不会做，于是「神」给你了一份代码。

CODE：

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
struct node {
	int val, maxx = -1;
	priority_queue<int> q;
} tree[N << 2];
inline void push_up(int k) {
	tree[k].maxx = max(tree[2 * k].maxx, tree[2 * k + 1].maxx);
	if (!tree[k].q.empty()) {
		tree[k].maxx = max(tree[k].maxx, tree[k].q.top());
	}
}
inline void update(int k, int l, int r, int x, int y, int z) {
	if (l == x && r == y) {
		tree[k].q.push(z);
		tree[k].maxx = max(tree[k].maxx, z);
		return;
	}
	int mid = (l + r) >> 1;
	if (y <= mid) {
		update(2 * k, l, mid, x, y, z);
	} else if (x > mid) {
		update(2 * k + 1, mid + 1, r, x, y, z);
	} else {
		update(2 * k, l, mid, x, mid, z);
		update(2 * k + 1, mid + 1, r, mid + 1, y, z);
	}
	push_up(k);
}
inline void erase(int k, int l, int r, int x, int y, int z) {
	if (y < l || x > r || tree[k].maxx < z) {
		return;
	}
	if (!tree[k].q.empty() && tree[k].q.top() == z) {
		tree[k].q.pop();
		if (l < x) {
			update(k, l, r, l, x - 1, z);
		}
		if (r > y) {
			update(k, l, r, y + 1, r, z);
		}
		if (l < r) {
			push_up(k);   //。。。改成函数总是好的。
		} else {    //你猜是不是只剩下 l = r 的情况了
			tree[k].maxx = -1;
			if (!tree[k].q.empty()) {
				tree[k].maxx = tree[k].q.top();
			}
		}
		return;
	}
	int mid = (l + r) >> 1;
	erase(2 * k, l, mid, x, y, z);
	erase(2 * k + 1, mid + 1, r, x, y, z);
	push_up(k);
}
inline int query(int k, int l, int r, int x, int y) {
	if (l == x && r == y) {
		return tree[k].maxx;
	}
	int mid = (l + r) >> 1;
	int res = -1;
	if (!tree[k].q.empty()) {
		res = tree[k].q.top();
	}
	if (y <= mid) {
		res = max(res, query(2 * k, l, mid, x, y));
	} else if (x > mid) {
		res = max(res, query(2 * k + 1, mid + 1, r, x, y));
	} else {
		res = max({res, query(2 * k, l, mid, x, mid), query(2 * k + 1, mid + 1, r, mid + 1, y)});
	}
	return res;
}
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1) {
			int k;
			cin >> k;
			update(1, 1, n, l, r, k);
		} else if (op == 2) {
			int x = query(1, 1, n, l, r);
			if (x != -1) {
				erase(1, 1, n, l, r, x);
			}
		} else {
			cout << query(1, 1, n, l, r) << "\n";
		}
	}
	return 0;
}

线段树套堆思路分析

在你的苦苦哀求下，「神」告诉了你具体思路。

温馨提醒：这道题的线段树与普通线段树有一点点区别，且在观赏「神」的思路的时候请看完一个板块再思考，因为有些问题可能会在其他操作中讲到。

「神」说其他题解中说这个思路为标记永久化。

$[1, n]$ 每一个位置都有一个可重集合（就是堆）。

对于操作 $1$ ，即在区间 $[l, r]$ 中每一个堆都插入一个数 $k$ 。那么在线段树每一个点上维护一个堆，代表这个点所管辖的区间中有哪些数。那么在线段树中找到区间 $[l, r]$ 直接在这个点所维护的堆中插入 $k$ 即可。
对于操作 $3$ ，即查询区间 $[l, r]$ 中所有堆中最大数。那么线段树上每一个点再维护一变量 $\text{maxx}$ ，表示这个点所维护的区间中的所有堆中的最大数。查询的时候直接返回即可。
对于操作 $2$ ，即把区间 $[l, r]$ 中每一个堆都删除一个 $[l, r]$ 的所有堆中的最大数。

显然操作 $2$ 最难处理。那我们可以先手动添加一个操作 $3$ ，设返回的答案为 $x$ ，那我们只需要在区间 $[l, r]$ 中每一个堆里面删除一个 $x$ 。那么我们设线段树上第 $p$ 个点的堆中的最大值为 $v$ 。

当 $v > x$ 时，堆中可能存在 $x$ ，继续递归处理子区间。
当 $v = x$ 时，堆中最大数就是 $x$ ，直接弹出就好。
当 $v < x$ 时，堆中不可能存在 $x$ ，结束递归。

那么 $v > x$ 的情况最后一定会变成等于或者小于的情况，所以其实我们只用讨论 $v = x$ 时该怎么办就好，但是很显然直接弹出。但是就当你激动地准备提交代码时，惊奇的发现样例过不了，于是你再次请求「神」帮你调试代码，但是「神」告诉你还有一种情况。你诧异至极，顿时如梦初醒。

当 $v = x$ 时，假设 $p$ 所维护的区间为 $[l_1, r_1]$ ，操作区间为 $[l, r]$ ，显然 $[l, r] \subset [l_1, r_1]$ ，是不是发现问题了？你其实把 $[l_1, l) \cup (r, r_1]$ 的 $x$ 都给删除了，不好，怎么办？直接在这两个区间里面用操作 $1$ 加回去就好了，就是这么暴力。

总时间复杂度为 $\mathcal{O}(q \log^2 n)$ 。

为什么是 $\mathcal{O}(\log^2 n)$ 呢？插入和查询时就不用多说，只需要聊聊删除操作。首先线段树的深度为 $\log n$ ，并且每次删除都可能会有两个区间的插入操作。但是你会发现中间的那个区间就不用更新了。于是就相当于递归左儿子和右儿子且你遍历的深度越大，那么儿子的深度就越小，平摊一下就差不多总深度为 $\log n$ ，再算上优先队列的 $\log n$ 就 $\log^2 n$ 了。

注意：

别忘了 $\text{maxx}$ 在插入、删除操作的时候需要更新。插入的时候只需要再取 $\max(\rm maxx, k)$ 。在删除操作中， $v = x$ 时需要将 $\rm maxx$ 重新赋值成堆顶元素再取左右儿子最大值。
注意取堆顶元素时要先判断堆是否为空。
如果堆为空那么这个点的答案为 $\max(-1, \rm maxx_l, maxx_r)$ 。

具体实现还是看上面的代码吧。~~突然感觉这道紫还挺水的，我赛时怎么没场切呢。~~

如果有错别字可以在讨论区威胁笔者修改。如果有疑问可以绑架作者并打破砂锅问到底。

以前从来没见过这种题和这种线段树，分析一下这种题目的本质是什么，如何举一反三应对类似的“线段树标记永久化套数据结构”的题目。

Answer 1

这题的核心并不是“线段树里放一个堆”这么简单，而是：

把每次区间插入看成一个带权区间对象，用线段树永久保存这些对象；每个位置的状态，由根到叶路径上所有对象共同决定。

操作 2 又恰好具有“删除全局极值、相同值副本不可区分、区间删去后仍是若干区间”的性质，因此可以对区间对象进行剪切。

一、先把题目换一种语言

对每个位置 $i$ ，维护一个可重集 $A_i$ 。

操作 1：

\forall i\in[l,r],\quad A_i\leftarrow A_i\uplus\{k\}

可以把它理解成创建了一个“区间记忆对象”：

e=(l,r,k)

它在区间 $[l,r]$ 内的每个位置贡献一个 $k$ 。

于是，位置 $i$ 的可重集，实际上就是：

A_i=\{\!\{k_e\mid i\in [l_e,r_e]\}\!\}

也就是说，每个位置的元素来自所有覆盖它的区间对象。

操作 3 就是：

\max_{i\in[l,r]}\max A_i

操作 2 则是：

求出 $x=\max_{i\in[l,r]}\max A_i$
对每个满足 $\max A_i=x$ 的位置，删除一个 $x$ 。

所以这题本质上是：

动态维护一批带权区间，每个点拥有所有覆盖它的区间权值；支持查询一段位置中的最大权值，并从目标区间内剪掉一层最大权值。

二、为什么普通懒标记不好做

假设在区间 $[1,n]$ 上依次插入：

5,\ 5,\ 3,\ 8

如果只维护一个普通的最大值懒标记 $8$ ，那么删除一个 $8$ 后，需要知道下一个最大值是 $5$ 。

因此不能只保存一个数，必须保存所有尚未删除的区间标记，并且保留重数。

自然就需要一个可重集合。由于只关心最大值，并且删除的也是最大值，所以优先队列正合适。

但如果采用普通懒标记下传：

一个节点中可能积累很多区间标记；
一旦需要局部操作，就要把整个堆复制或下传给左右儿子；
复杂度和空间都会失控。

所以这里不下传标记，而是采用“标记永久化”。

三、标记永久化到底是什么

普通懒标记的想法是：

标记暂时放在高层节点，以后有需要再推给儿子。

标记永久化的想法是：

这个标记本来就代表整个节点区间，因此永远放在这个节点，不再下传。查询时主动统计沿途的所有标记。

注意它和“可持久化数据结构”没有关系。

“永久”指的是标记不向下推，不是保存历史版本。

1. 区间插入的存储方式

在线段树中，将区间 $[l,r]$ 分解成 $O(\log n)$ 个线段树节点。

例如：

[3,10]=[3,4]\cup[5,8]\cup[9,10]

对于每个被完整覆盖的节点 $u$ ，将 $k$ 插入节点自己的堆 $H_u$ 。

堆里的一个元素 $k$ 表示：

节点 $u$ 对应区间 $I_u$ 中的每个位置，都拥有一个 $k$ 。

于是对任意叶子 $i$ ，它的真实可重集为：

A_i=\biguplus_{u\text{ 在根到 }i\text{ 的路径上}}H_u

这是整套做法最重要的不变量。

2. 节点维护什么

对每个线段树节点 $u$ ，维护：

$H_u$ ：直接存储在该节点的区间标记；
$\operatorname{top}(H_u)$ ：节点自身标记中的最大值；
$mx_u$ ：节点子树内出现过的最大值。

有：

mx_u= \max\left( \operatorname{top}(H_u), mx_{\mathrm{left}(u)}, mx_{\mathrm{right}(u)} \right)

其中空堆和空子树的最大值视为 $-1$ 。

要注意：

$mx_u$ 只统计存放在 $u$ 及其后代节点中的标记，不统计祖先节点的标记。

祖先标记需要在查询递归过程中额外考虑。

四、为什么区间查询能够直接做

查询区间 $Q=[l,r]$ 。

递归经过节点 $u$ 时， $H_u$ 中的每个标记都覆盖整个 $I_u$ ，所以只要：

I_u\cap Q\ne\varnothing

节点堆顶就可能成为答案。

如果某个儿子的区间被查询区间完整包含，就可以直接使用儿子的 $mx$ 。

因此查询过程实际上统计了两类信息：

查询路径上的祖先永久标记；
完整包含在线段树查询分解中的子树信息。

这也是代码里为什么先取：

cpp
res = tree[k].q.top();

再递归查询儿子的原因。

五、操作 2 为什么是整题的精华

首先查询：

x=\max_{i\in[L,R]}\max A_i

然后需要对所有满足局部最大值为 $x$ 的位置删除一个 $x$ 。

考虑线段树节点 $u$ ，对应区间 $I_u$ 。

情况一： $mx_u<x$

说明节点子树中根本没有 $x$ ，直接跳过。

cpp
if (tree[k].maxx < x) return;

情况二：节点自己的堆顶等于 $x$

即：

\operatorname{top}(H_u)=x

这个 $x$ 是一个覆盖整个 $I_u$ 的区间标记。

对于任意：

p\in I_u\cap[L,R]

由于节点标记给位置 $p$ 提供了一个 $x$ ，所以：

\max A_p\ge x

另一方面， $x$ 是整个查询区间的最大值，所以：

\max A_p\le x

因此：

\max A_p=x

也就是说，交集中的每个位置都正好应该删除一个 $x$ 。

于是可以直接：

cpp
tree[u].heap.pop();

它会从整个 $I_u$ 删除一层 $x$ 。

但删除范围太大了

真正需要删除的只是：

I_u\cap[L,R]

但弹出节点标记会影响整个 $I_u$ 。

因此把不该删除的部分补回来：

I_u\setminus[L,R]

因为两个区间作差最多得到两个区间：

I_u\setminus[L,R] = [I_u^L,L-1]\cup[R+1,I_u^R]

所以分别在左侧、右侧重新插入一个 $x$ 。

这就是代码中的：

cpp
if (l < x) update(k, l, r, l, x - 1, z);
if (r > y) update(k, l, r, y + 1, r, z);

本质是：

先把整块标记删除，再把查询区间之外的部分补回去。

这可以称为“区间对象剪切”。

六、为什么可以随便删除这个 $x$

某个位置可能同时有多个值为 $x$ 的记忆，例如：

A_i=\{2,5,5,5\}

题目只要求删除一个 $5$ ，并不关心删除的是哪一次操作产生的 $5$ 。

因此所有相同权值的副本都是不可区分的。

这意味着：

只要从该位置覆盖到的任意一个 $x$ 标记中删掉一份，结果可重集就是正确的。

代码有时删除节点自身的 $x$ ，有时递归到后代删除另一个 $x$ ，都没有关系。

如果题目给每个记忆一个编号，并要求删除特定编号的记忆，这个做法就不能直接成立。

七、一个容易混淆的细节

原题解中提到：

节点堆顶 $v>x$ 时继续向下递归。

严格来说，如果这里的 $v$ 指的是节点自己堆的堆顶，并且节点区间与查询区间相交，那么：

v>x

其实不可能发生。

因为节点自己的标记覆盖整个节点区间，只要它和查询区间有交集，交集中的位置就拥有一个 $v>x$ ，这会与 $x$ 是查询区间最大值矛盾。

真正可能大于 $x$ 的是：

mx_u

因为 $mx_u$ 统计整个节点区间，较大的值可能只出现在查询区间之外的后代中。

所以更准确的分类是：

$mx_u<x$ ：直接剪枝；
$\operatorname{top}(H_u)=x$ ：删除当前永久标记；
$\operatorname{top}(H_u)<x$ ：目标 $x$ 只可能位于后代，递归；
$\operatorname{top}(H_u)>x$ ：对相交节点不可能。

八、复杂度需要更严谨地理解

原题解说删除操作单次是 $O(\log^2 n)$ ，这并不是严格的最坏情况。

例如：

对每个位置单独插入一个 $1$ ；
然后对整个区间执行一次删除。

这一次删除会访问所有叶子，单次复杂度可以达到 $O(n)$ 。

正确的理解是：

总复杂度是均摊的 $O(m\log^2 n)$ ，而不是每次删除都严格 $O(\log^2 n)$ 。

为什么总复杂度仍然正确

每次操作 1 会产生 $O(\log n)$ 个堆元素。

删除过程中，弹出的节点两两不具有祖先后代关系，因为在某个节点弹出后就直接返回，不再递归它的后代。

所以被弹出节点对应的区间互不相交。

对于固定查询区间 $[L,R]$ ：

最多只有一个被弹出节点跨过左边界 $L$ ；
最多只有一个被弹出节点跨过右边界 $R$ ；
其余被弹出的节点都完整包含在 $[L,R]$ 中，不需要补回。

因此每次删除最多产生两个需要补回的区间。

每个补回区间在线段树上拆成 $O(\log n)$ 个新堆元素，所以整个操作序列中创建的堆元素总数为：

O(m\log n)

每个堆元素：

被插入一次；
最多被弹出一次；
单次堆操作为 $O(\log m)$ 。

再考虑线段树递归和维护，整体可以控制在：

O(m\log n\log m)

在 $n,m$ 同阶时通常写作：

O(m\log^2 n)

空间复杂度为：

O(m\log n)

九、这种题应该如何识别

遇到下面几个特征时，可以考虑“标记永久化套数据结构”。

特征 1：一次操作创建一个区间对象

例如：

给区间中每个位置添加一个权值；
给区间中每个位置添加一种颜色；
给区间中每个位置添加一个任务；
一个权值为 $w$ 的区间开始生效。

重点是：

更新不是简单修改一个数，而是创建了一个以后可能需要单独删除、统计的对象。

特征 2：每个点的状态由所有覆盖它的对象决定

例如：

f(i)=\max\{w_e:i\in I_e\}

或者：

f(i)=\min\{w_e:i\in I_e\}

又或者需要知道覆盖点 $i$ 的对象数量、颜色集合等。

这类问题也称为动态区间 stabbing：

给定一个位置，查询所有覆盖这个位置的区间对象。

特征 3：对象不能压缩成普通懒标记

如果只需要区间加、区间和，可以把所有操作压缩成一个加法标记。

但如果需要：

删除其中一个最大值；
保留重复值数量；
查询次大值；
按编号删除对象；
查询第 $k$ 大；

就不能只保存一个标量，必须维护对象集合。

此时节点内需要套数据结构。

特征 4：查询信息可以从局部摘要合并

本题查询的是最大值：

\max(\text{左侧答案},\text{右侧答案},\text{当前节点标记})

最大值具有很好的可合并性。

类似适用的还有：

最小值；
按位或；
按位与；
是否存在；
某些可结合的摘要。

但如果查询的是：

\sum_i \max A_i

就没有这么简单。

因为区间对象可能覆盖许多位置，不能只用一个节点最大值计算所有点的最大值之和。

特征 5：局部删除后，对象支持低复杂度切割

本题一个区间减去另一个区间，最多剩两个区间：

[a,b]\setminus[l,r]

最多是：

[a,l-1],\quad [r+1,b]

因此可以删除整块，再补回左右两块。

这是本题能做的一个关键几何条件。

如果删除后剩余集合会变成大量碎片，这种方法就很容易失控。

十、设计这类数据结构的一套固定流程

以后遇到类似问题，可以按以下顺序思考。

第一步：把更新写成“对象”

不要先想线段树节点怎么维护。

先问：

一次更新究竟创建了什么对象？

本题创建：

(\text{支持区间},\text{权值})

即：

([l,r],k)

第二步：写出单点状态

问：

位置 $i$ 的答案，由哪些对象决定？

本题：

A_i=\{\!\{k_e:i\in I_e\}\!\}

然后：

f(i)=\max A_i

第三步：考虑对象的线段树规范分解

区间对象可以拆成 $O(\log n)$ 个线段树节点。

于是约定：

每个对象只存放在其规范分解得到的节点中。

不要把它继续下传到所有叶子。

第四步：选择节点内部数据结构

根据需要选择：

需求	节点内部结构
只插入、取最大、删最大	大根堆
只插入、取最小、删最小	小根堆
任意值删除	`multiset`
按对象编号删除	双堆懒删除或哈希计数
查询排名、前驱后继	平衡树
权值离散，查询计数、第 $k$ 大	树状数组、权值线段树
需要撤销	回滚栈、可撤销结构

本题只需要删除最大值，因此堆已经足够。

第五步：明确节点摘要

节点自身的数据结构只表示“直接挂在节点上的对象”。

还要维护整个子树的摘要：

summary_u= merge(local_u,summary_{lc},summary_{rc})

本题为：

mx_u=\max(top_u,mx_{lc},mx_{rc})

第六步：查询时处理祖先贡献

永久标记不会下传，因此查询一个叶子或子区间时，不能只看目标节点。

必须考虑所有祖先节点上的永久标记。

典型方式有两种：

查询递归时不断把祖先贡献合入答案；
维护一个 carry 参数，表示根到当前节点积累的信息。

第七步：破坏性操作先确定目标值

本题操作 2 不直接递归删除，而是先查询得到：

x

有了这个全局极值，才可以强力剪枝。

这是一个很常见的套路：

先查询目标极值，再进行带目标值的定向修改。

类似结构还经常用于：

删除区间最大值；
修改所有等于区间最小值的位置；
找到最早冲突位置再局部修复；
对达到某个阈值的节点递归处理。

第八步：寻找“整块处理”的充分条件

本题的充分条件是：

top(H_u)=x

因为该标记覆盖整个节点区间，可以整块删除。

数据结构优化经常依赖这种思想：

找到一个条件，一旦满足，就不再递归到叶子，而是对整个节点一次完成操作。

这和线段树 Beats 有一点精神上的相似性，但机制不同：

Beats 依靠最大值、次大值等统计量判断整块修改；
本题依靠永久区间对象，直接删除整个节点标记。

第九步：处理整块操作的副作用

整块删除影响了查询区间之外的位置。

于是把对象在补集上的部分恢复。

本质是：

\text{新对象支持集} = \text{旧支持集}\setminus\text{修改区间}

如果这个集合仍能由常数个同类对象表示，做法就很有希望。

十一、哪些变形还能用

变形一：查询最小值，删除一个最小值

把大根堆换成小根堆，maxx 换成 minn，思路基本相同。

变形二：支持按值删除指定的 $x$

如果要从区间内所有包含 $x$ 的位置删除一个 $x$ ，仍可能采用类似剪切。

但节点内不能只依赖堆顶，需要判断某个值是否存在并删除，通常改用：

multiset；
值到次数的映射；
离散化后的权值数据结构。

复杂度会更高。

变形三：每个区间对象带唯一编号，支持撤销某次插入

节点堆中保存：

(\text{权值},\text{编号})

删除指定编号时，可以使用：

主堆；
删除堆；
两堆堆顶相同时同时弹出。

这是经典懒删除。

不过如果对象被操作 2 剪切过，还需要维护编号对应的多个区间碎片，问题会明显复杂。

变形四：只查询单点最大值

这会更简单。

区间对象仍放在线段树规范节点中，查询位置 $i$ 时只需沿根到叶路径取所有堆顶最大值。

不需要维护子树 maxx。

变形五：动态区间集合，查询某点被哪些区间覆盖

这其实是同一模型。

每个节点存放完整覆盖该节点的区间对象；单点查询扫描根到叶路径上的所有节点数据结构。

区别只是内部容器和查询内容不同。

十二、哪些变形会直接破坏这个做法

1. 删除每个位置自己的最大值

如果操作变成：

对区间中每个非空位置，删除它自己的最大值。

那么不同位置删除的值可能不同：

5,7,2,9,\ldots

不再有一个统一目标 $x$ ，无法使用 maxx < x 剪枝，也很难整块删除同一标记。

2. 相同值副本有身份区别

如果必须删除特定来源的 $x$ ，就不能任意选择一个覆盖节点的 $x$ 弹出。

本题成立依赖：

相同权值的副本在可重集中完全不可区分。

3. 查询区间内所有点最大值之和

本题只查询：

\max_i \max A_i

最大值的最大值仍然是最大值。

但：

\sum_i\max A_i

需要知道每个永久标记具体影响了多少位置、不同标记之间如何覆盖，节点只维护一个 maxx 远远不够。

4. 删除集合不是区间

如果删除的是：

任意点集；
按某个复杂条件筛出的点；
大量离散位置；

那么一个区间对象被剪切后可能变成很多碎片，永久标记结构会快速膨胀。

5. 区间操作有严格时间顺序

本题每个位置维护的是可重集，插入顺序没有意义。

如果操作变成字符串拼接、函数复合等非交换操作，那么根到叶路径上的标记需要按时间顺序组合，普通堆无法处理。

十三、最推荐的直观模型：覆盖图层

可以把每次操作 1 想象成在数轴上铺了一条图层：

横向范围是 $[l,r]$ ；
图层高度是 $k$ ；
同一个高度允许有多层。

某个位置的最大苦涩值，就是该位置最高的图层高度。

操作 3：

看查询区间中出现的最高图层。

操作 2：

找到查询区间中的最高高度 $x$ ，然后从所有能看到高度 $x$ 的位置撕掉一层 $x$ 。

线段树节点的堆，就是存放“完整横跨这个节点区间”的图层。

当要只撕掉图层中间的一部分时：

先把整条节点图层拿掉；
把左边没撕的部分铺回去；
把右边没撕的部分铺回去。

这正是代码的全部本质。

十四、最后总结成一句判定口诀

看到一题同时满足：

区间创建对象，单点由覆盖对象决定；对象不能压成单标记，查询可以合并摘要；修改针对统一极值，相同对象可互换；局部修改后支持集仍能拆成少量区间。

就应该考虑：

\boxed{\text{线段树规范分解}+\text{标记永久化}+\text{节点内数据结构}+\text{区间对象剪切}}

而这题中：

规范分解解决区间插入；
永久标记避免大堆下传；
优先队列维护重复最大值；
maxx 负责子树剪枝和查询；
“弹出整块，再补回两边”解决局部删除；
全局最大值 $x$ 保证整块删除的正确性；
相同值副本不可区分保证删除哪一份都可以。

Câu hỏi