CF1408H Rainbow Triples 题解

zrl123456 · 2025-11-17 15:33:54 · 题解

:::::info[题目基本信息] 考察：图论，贪心，线段树（3300）。
题目简介：
给定 \{a_n\}，求 m 的最大值使得存在 m 个三元组 (x_i,y_i,z_i) 满足：

• \forall i\in[1,m],1\le x_i<y_i<z_i\le n
• \forall i\in[1,m],a_{x_i}=a_{z_i}=0,a_{y_i}\ne 0
• \forall i,j\in[1,m],i\ne j,a_{y_i}\ne a_{y_j}
• \forall i,j\in[1,m],i\ne j,\{x_i,y_i,z_i\}\cap\{x_j,y_j,z_j\}=\varnothing

数据范围：

• 1\le n\le 5\times 10^5
• \forall i\in[1,n],0\le a_i\le n

  :::::

  每一个元素权值三元组都是 $(0,x,0)$ 的样子，贪心地想，我们肯定会让位于三元组左边的 $0$（下文简称左 $0$）尽可能的靠左，右边的（下文简称右 $0$）尽可能的靠右，所以每当有一个右 $0$ 位于左 $0$ 的左边那么我们交换他们肯定不劣，所以我们令前一半 $0$ 是左 $0$，后一半 $0$ 是右 $0$。 现在我们考虑对每一个颜色（$a$ 序列）建一个左部点，对每一个相对位置（$1$ 到 $m$）建一个右部点，那么颜色 $col$ 连向相对位置 $pos$ 当且仅当：
• - $a_i=col
  • \displaystyle\sum_{i=1}^{pos-1}[a_i=0]\ge pos
  • \displaystyle\sum_{i=pos+1}^n[a_i=0]\ge n-pos+1

直接暴力跑匹配可以做到 \Theta(n^{2.5}\log n) 的复杂度，但是和正解几乎一点关系没有。
我们考虑观察一下一个颜色所连的点有什么特点，注意到一个位置要么左 0 全在他的左边，要么右 0 全在他的右边，那么分别只需要满足 \displaystyle\sum_{i=1}^{pos-1}[a_i=0]\ge pos 和 \displaystyle\sum_{i=pos+1}^n[a_i=0]\ge n-pos+1 即可，那么对于任意一个位置，他可以作为一段前缀或一段后缀，那么全部并起来就会变成一段前缀和一段后缀。
唉这不就是 ARC076F 吗，那个题的时间复杂度是 \Theta(n\log n) 的（具体见 我的题解），那么我们的时间复杂度是 \Theta(n\log^2n) 的，可能能过去但是我被卡了。
然后我们考虑去掉二分的 log，我们注意到这个二分屁用没有，因为有多少右部点是不影响答案的，所以我们直接把二分扔掉，然后我们就解决了此题。

时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

code