China Final 2016 C 题瞎扯淡

周末去上海大学的 ACM/ICPC China Final，新的一赛季也结束了，出了个 “Mr. Panda and Strips” 直接身败名裂（一个奇怪的梗：我怀疑出 C 这个题的人啊，他不会做题啊？（x

大概不会补其它题的题解了暂时（看情况吧。。。

这破题出的刚想出 idea 的时候一群人讨论了下，finalize 了一个 $O(N^2 \lg N)$ 的做法，大致的思路是枚举第一个区间的左右边界 $L$ 和 $R$，然后去维护第二个区间，对于第二个区间，我们维护一个区间的集合 $S$，我们把区间内的元素表示成三元组 $(l, r, m)$，表示如果第二段区间的起点 $L'$ 是处于 $[l, r]$ 这个区间内的话，它可以向右延伸的右边界就是 $m$，也就是说，对于确定了 $R$ 的情况下，最后的答案应该是

$$(R - L + 1) + \max_{k \in S} \left(m_k - l_k + 1\right)$$

我们考虑增加 $R$ （双指针），当 $R$ 增加 $1$ 的时候，你会发现，有一些区间包含了数字 $a_R$，那么我们要考虑把这些区间拆成多个区间，对于一个区间 $(l, r, m)$，如果存在 $k \in [l, m]$ 使得 $a_k = a_R$ 的话，我们就把它拆掉。我们令 $a_p = a_R$，对于小于 $p$ 的来说，我们可以拆成一个区间 $(l, p - 1, p)$，对于大于 $p$ 的来说，我们可以拆成区间 $(p + 1, r, m)$。那么，当我们 $R$ 增加的时候，我们逐个地去看所有满足条件的 $p$，维护一个 ordered set 去查找包含 $p$ 的区间，对于每个 $p$，有且只有一个对应的需要拆分的区间（注意一点就是集合 $S$ 中的区间，$l$, $r$ 和$m$ 都是严格递增的，而且没有 $[l, r]$ 交集）。

这样搞一搞就 $O(N^2 \lg N)$ 了？啊，什么？你觉得这样不优美，那么这里不优美的地方在哪啊！还不是要用 ordered set 去找要拆的区间么！那我反过来做 （$R$ 从大到小枚举）是不是就变成了区间合并问题了？那么区间合并问题是不是就是并查集合并省下一个 $\lg N$ 了？

那么，我们就把 $R$ 从大到小枚举吧。。。首先我们先来算两个数组的值

• 一个是 $b$, $b_i$ 表示大于 $i$ 并且 $a_p = a_i$ 的最小的位置 $p$。
• 另外一个是 $c$, $c_i$ 表示对于 $i \leq k \leq p$ 条件下 $\min{b_k} \leq p$ 的最大的位置 $p$。

当我们 $R$ 变小的时候，就会有两个（只会有两个）区间发生了合并，大概上就是区间 $(l, p - 1, p)$ 和 $(p + 1, r, m)$ 被修改成了区间 $(l, p - 1, m_1)$ 和区间 $(p, r, m_2)$。如果我们枚举 $p$ 的时候是从大到小的话，这里 $m_2$ 应该就等于 $m$ 了，对于 $m_1$ 来说，我们考虑先预处理出 $[l, p - 1]$ 里面可以向右扩展的最大距离（这里其实就是 $b_k$ 的最小值），那么 $m_1$ 就可以通过 $b$ 数组和现在有大于 $p$ 的最小的不能选位置 $q$ （在第一段中出现过），还有数组 $c$，来更新答案。

$$m_1 = \min(\min_{l \leq k \leq p - 1}(b_k), q, c_{p + 1})$$

对于这个合并的做法，我们可以直接利用并查集维护 $[l, r]$ 这个集合，然后并查集的值存 $m$ 就可以表示区间 $(l, r, m)$ 了。总体复杂度 $O(N^2 \cdot \alpha(n))$。