[APIO2023] 序列

题意

求一个序列的子区间中中位数出现的最多次数。

题解

考试的时候被薄纱了，感觉自己太弱了/kk

首先题目求的是中位数，这种东西有一个经典的操作，将原序列转为 \(01\) 序列。

考虑枚举中位数 \(x\)，将小于 \(x\) 的数设为 \(-1\)，等于 \(x\) 的设为 \(0\)，将大于 \(x\) 的设为 \(1\)，设新数组为 \(b_i\) 。
容易发现对于一个区间 \([l,r]\) 来说，设 \(0\) 有 \(c_0\) 个，\(1\) 有 \(c_1\) 个，\(-1\) 有 \(c_2\) 个，合法当且仅当 \(|c_1+c_2| \leq c_0\) 。

我们考虑固定 \(c_9\) ，我们将区间 \([l,r]\) 分割为 \([l,L][L,R][R,r]\)，\(L\) 和 \(R\) 是区间中 \(0\) 的最后和第一个位置。
显然我们是要在 \([l,L]\) 和 \([R,r]\) 中分别选取一段后缀和前缀，使得其符合条件。
知道每移动一个位置就只会变化 \(1\) ，所以我们知道 \(min\) 和 \(max\) 即可。
现在题意转化为要求满足 \(|[lmin,lmax]+[rmin,rmax]+\sum_{i=L}^{i \leq R}b_i| \leq c_o\)
我们知道中间这一坨可以转化为前缀和相减，设前缀和为 \(s\)，就可以将条件转化为 \(|[lmin-s_{L-1},lmax-s_{L-1}]+[rmin+s_{R},rmax+s_{R}]| \leq c_o\)
转加为减。
将条件转化为 \(|[s_{L-1}-lmax,s_{L-1}-lmin]-[rmin+s_{R},rmax+s_{R}]| \leq c_o\)
将两个区间设为 \([l_1,r_1],[l_2,r_2]\)，相当于在两个区间中各选一个点，使得两点之间距离最小，显然有两种情况。
1.两个区间有交，距离为 \(0\)，即满足 \(l_1 \leq r_2\) 且 \(l_2 \leq r_1\) 。
2.两个区间无交，距离为 \(\max (l_1-r_2,l_2-r_1)\)

注意到我们求最小的距离是为了判断能否做到小于等于 \(c_0\) 。
我们实际上只是要做这样一个判断是要判断最接近的两个端点的距离是否超过 \(c_0\) 。
这样我们会发现还有另一种方式可以判断即判断 \([l_1-c_0,r_1+c_0],[l_2,r_2]\) 是否有交。
注意到 \(c_0\) 可以写成 \(pos_r-pos_l+1\) 的形式，所以可以再转化为 \([l_1-(1-pos_l),r_1-(1-pos_l)],[l_2-pos_r,r_2+pos_r]\) 是否有交。
容易发现 \(l\) 区间只和 \(l\) 有关了，题目转化为我们要求最远的一个与这东西有交的区间，这样就转化为了一个二维偏序问题，离线扫描线解决即可。code