0%

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$,维护一个oredered 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))$。