本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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\}=\arnothing$

数据范围：

• $1\le n\le 5\times 10^5$
• $\forall i\in[1,n],0\le a_i\le n$ ::::: $m$ 的取值显然具有可二分性，考虑先二分。
  每一个元素权值三元组都是 $(0,x,0)$ 的样子，贪心地想，我们肯定会让位于三元组左边的 $0$（下文简称左 $0$）尽可能的靠左，右边的（下文简称右 $0$）尽可能的靠右，所以每当有一个右 $0$ 位于左 $0$ 的左边那么我们交换他们肯定不劣，所以我们令前一半 $0$ 是左 $0$，后一半 $0$ 是右 $0$。
  现在我们考虑对每一个颜色（$a$ 序列）建一个左部点，对每一个相对位置（$1$ 到 $m$）建一个右部点，那么颜色 $col$ 连向相对位置 $pos$ 当且仅当：
• $\exists i\in[1,n]$ 满足：
  • $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