Luogu6854 Tram

发表于 分类于 ， ， 阅读次数：

The 400th Blog.

题意 :

定义一个序列(可重集合) 是好的，当且仅当 :

  • ① 对于任意的 ，有
  • ② 对于任意的 ，要么 ，要么在 中出现恰好 次。

给出一个序列 ，问有多少个连续区间是好的。

，时限 。

有意思的题。

做本题的关键是瞄准“连续区间”的性质，不要仅当做无序可重集合来考虑。

条件①等价于要求求值域连续。

条件②则非常苛刻，在满足条件②的情况下，只需要查看最值就能知道是否满足条件①。

先来考虑如何计算满足条件②的区间个数。

考虑枚举右端点，用数据结构维护每个左端点。

对于数 ，可选的左端点区间是第 个 和第 个 之间的部分，以及第 个 和右端点之间的部分。(均为左开右闭)

当在右侧加入一个新数 时， 的可行区间会产生变化，容易使用类似双指针的方法求出。

那么就转化成了如下的问题 :

维护若干“双线段并”，支持下列操作 :

  • 修改其中一个双线段并。

  • 查询所有双线段并的交集。

可以在每个“双线段并”没覆盖的地方 ,则可行的位置为 ，且是最小值。

由于条件非常苛刻，我们进一步猜想，满足条件②的区间个数，有没有一个优美的上界呢?

考虑一个好的集合应该长什么样，答案是 之间的数，且满足 出现 次。下面我们以 代指这样的集合。

显然有 。

从每个右端点向左扩展，假设目前的合法区间是 ,则下一个合法区间至少是 或者

当 时，易证 。

这样我们就得到了一个粗略的上界 。

若暴力对每个满足②的区间查询最值检验，就得到一个 的做法。

事实上，可以证明好区间的个数是 的。

考虑从小到大按照权值顺序插入数。

假设我们要插入 个 ，且目前的序列中有 个好区间。为了方便我们可以认为空序列也是好的。

考虑新序列中好区间的来源。

  • 原来是好区间，没有被插入新数。
  • 原来是好区间，中间恰被插入了 个 。
  • 由连续的 个 和没有被插入新数的好区间贴合而成。

前两者显然是由旧的好区间衍生而得， 个。

将连续的 个 称为一块，每一块能够贴出来的好区间肯定是 这样的，为 个。

新增好区间即为 个。即好区间总数为 。

这样，就能证明上面那个做法的复杂度为 了。