「from CommonAnts」「JXOI2017」T3 颜色 的一个思路

liu_cheng_ao 2017-05-06 16:21:14 2018-02-04 9:00:07

题目描述

可怜有一个长度为 n 的正整数序列 A_i ,其中相同的正整数代表着相同的颜色。
现在可怜觉得这个序列太长了,于是她决定选择一些颜色把这些颜色的所有位置都删去。
删除颜色 i 可以定义为把所有满足 A_j=i 的位置 j 都从序列中删去。
然而有些时候删去之后,整个序列变成了好几段,可怜不喜欢这样,于是她想要知道有多少种删去颜色的方案使得最后剩下来的序列非空且连续。
例如颜色序列 \{1,2,3,4,5\} ,删除颜色 3 后序列变成了 \{1,2\} \{4,5\} 两段,不满足条件。
而删除颜色 1 后序列变成了 \{2,3,4,5\} ,满足条件。
两个方案不同当且仅当至少存在一个颜色 i 只在其中一个方案中被删去。

这题等价于:存在多少个区间使得区间内的所有颜色的位置之并恰为此区间。

定义一种颜色 c 对应的区间是 [l,r] ,当且仅当 A_l=A_r=c ,且 \forall i<l i>r, A_i\neq c

首先我们对问题做一个转化:建立一个有向图 G ,图上的一个点代表一种颜色,如果 \exists i<j<k 使得 A_i=A_k=u,A_j=v 则连有向边 (u,v)

那么,一个合法的区间对应于一个没有出边的连通子图,因为如果一个子图的所有颜色对应的位置没有组成区间,其中一定有空隙,那么要么这个子图中有一条连向该位置颜色的边,要么子图以这个位置为界左右不连通。

问题转化成了:求没有出边的连通子图数目。

几个引理:
引理 0 若两种颜色 u v 对应的区间相交但互不包含,则 u v G 中对应的节点一定属于同一个强连通分量。
考虑区间端点可得有向边 (u,v) (v,u) 都存在,证毕。

引理 1 G 中若 u 能到达 v v 不能到达 u ,则 u 的区间包含 v 对应的区间。
与引理 0 类似。

现在对原图进行强连通分量缩点,显然缩点后同一个强连通分量里的颜色可以合成一种。故下面假设 G 是DAG。并且由引理 1 G 的传递闭包是本身。

由引理 1 一个点对应的区间一定包含它所有能到达的点的对应区间,又由DAG可知一个点能到达的所有节点的区间或者互不相交,或者互相包含,则我们可以建立一个有根树组成的森林,将这个点能到达的每一个对应一个极大子区间的点作为这个点的子树的根。

举个例子, \{1,2,3,2,1,2,4,9,8,9,10,8,5,4\} 对应的森林是这样:

那么,我们在森林上可以统计答案了。先加一个总根,于是每一个答案区间可以分解为一个的森林节点若干连续的孩子对应的区间之并,这些点满足:它们对应的区间依次相邻。

也就是对于一个节点的区间 [l,r] ,设里面的颜色是 \{c,S_1,c,S_2,c,...,c,S_n,c\} ,则这个节点对于答案的贡献是 \sum S_i 中的孩子数 (S_i 中的孩子数 +1)/2

其实到这里我们已经可以直接用 Tarjan 做到 O(n \log n) 复杂度了。不过似乎稍加改进就可以做到另一种 O(n\log n)

我们在序列上大致模拟那个森林先序遍历的过程。

要在区间的头尾分别加一个同样的新颜色表示森林的总根。

用链表存储每种颜色的位置。

从左往右扫,每次跳到下一个新颜色对应的位置,维护一个右端点单调递增的队列表示区间包含当前位置的颜色的集合

首先把队列首部右端点在当前位置左侧的颜色依次出队,并依次用当前它们对应的一段连续的孩子的个数更新答案,或者更新它们对应的那一段连续的孩子的个数。

那么首先判断这个颜色的右端点是不是在队列末的区间右端点的右侧,有的话就把队列末尾颜色出队,和当前颜色合并,对应的链表也合并。一直重复直到不能操作为止。接着把这种颜色插到队列末尾。

扫到末尾之后把总根的答案也算上,我们就在 O(n\log n) \log 来自链表合并,如果你不用链表而强行改用 RMQ 可以 O(n) )的时间内解决了本题。

不知道是否有错误。

不知道是否有老司机能利用这题性质比较优美的把 \log 干掉(目前可以使用 O(n)-O(1) RMQ 来做到这一点)。

UPD:今天听了 lzz 讲课,顿时感觉自己这题做法宛如智障……

我们的瓶颈是建图中把相交颜色合并的过程,把区间按 l ,从左到右加入,用栈和连通性图维护即可。