[SF-4] 算法杂谈 - 浅谈一类区间交集长度相关问题

· · 算法·理论

在我的做题范围中 1 个月内出现了两次这类题目，大抵可以说这是一个高频考点或者比较经典的一类问题。

一般这类问题是给定一些区间，然后询问一个区间与给定这些区间的贡献，贡献要求与交集长度相关。

此时枚举给定的区间一一算贡献往往会超时，而直接扫描线去维护往往会漏算或者重算、误算一些贡献。观察本质上是两个区间在做运算，所以可以枚举这两个区间的相对位置，设询问区间为 [ql,qr]，给定区间为 [l,r]，那么实际上只要考虑这四种情况：

即根据 ql,l 和 qr,r 的相对位置做出的四类分类讨论。往往化解到这一步会使问题简化许多。在实际中，部分问题没有必要做出四类分讨，可以根据题目的特性将四类压缩成两类或者三类。

接下来通过两道例题细讲一下这个方法。

NOIp 2024 T4

一道裸数据结构题，\log^2 做法很多，这里就不细讲了。主要来讲讲正解。

首先一条显然的结论是 dep(\text{LCA}^*(l,r))=\min_{l\le i\lt r}dep(\text{lca}(i,i+1))。那么对于 k=1 的特判以后，就可以将其转为序列问题了。转化后，问题变成：

询问一个区间内所有长度为 k 的子区间最小值的最大值。（注：这里 k 是转换后的 k）

那么显然的想法是建出一个小根堆笛卡尔树，以每个点为根的子树所代表的区间恰好是这个点能够在原序列上支配的区间。对于一个询问，查询所有与其交 \ge k 的区间的最大权值。

相信很多人在考场上一定能转化到这一步（不过笔者并没有，笔者想到了一个常数巨大的 \log^2 做法就直接做了，并没想如何优化）。但是卡在了下一步上。分类的动机已经在上文解释清楚了。注意到当 l\lt ql 时，只要满足 r-ql+1\ge k，即判断 r 和 ql+k-1 的大小关系。那么可以产生贡献的 r 一定在 [ql+k-1,n] 中，意味着是一段区间。那么可以对 l 扫描线，线段树维护这一过程。

剩下的情况是 ql\le l 的情况。显然 qr\lt r 时可以按照 l\lt ql 的处理方式处理。但是还是逃不了处理 ql\le l\le r\le qr。这里的 k 这维没办法被省掉。如果没办法省掉，那么可以转换一个思路，将 k 这维扫描线，其他维考虑是否可以优化。是可以的。对 k 从大到小扫描线，查询区间时只要查询左端点恰好在 [ql,qr-k+1] 即可。当然可能包含 ql\le l\le qr\lt r，那意味着可以不用倒着扫一遍。

就这样，我们通过分类，将原问题转换成两个简单的 ds 子问题。

MX - 02 B

不是所有人都有权限，那我大概说一下题意：

给定一个正整数序列 a，定义区间 [l,r] 的价值函数 w(l,r)=(r-l+1)·\min_{l\le i\le r}a_i。q 组询问，每次询问一个区间 [l,r] 中所有子区间的最大价值函数。

我们发现其实和上一题很像，但是唯一不同的是，上一题有一个 k 的限制，这题的价值函数与 len 相关。

发现对于查询区间包含给定区间或者被包含于给定区间的两种情况可以直接扫描线做。那么问题只剩下有交且没有包含的情况。

以 l\lt ql\le r\le qr 的情况为例，另外一种是完全相反的，可以倒着做。相当于对于定义域在 [l,r] 的函数 g(i)=-vi+(r+1)v 上取 g(ql) 的值。这可以对于 r 扫描线，李超树维护若干线段的每个位置最大值。

通过上述的讲解，相信您一定会有所收获。若此文章中存在漏洞，请及时指出并联系笔者。感谢您的支持！