中位数切分

 

https://ac.nowcoder.com/acm/contest/23106/F

和其他方法比起来,我写的方法可能不是那么优,但也不妨作为一种思路。

我们将比 $m$ 小的数设为 $1$,反之设为 $0$。

那么我们就将得到一个只包含 01 的数组。我们将这个数组求出其前缀和$S$。

对于区间 $(l ,r]$ 而言。只要我们满足 $S[r] - S[l] <= \frac{(r - l - 1)}{2}$ 条件即可。其中 $0 \le l < r \le n$。

我们将这个式子化简便可以得到这样的关系。 $(2 * S[r] - r) + 1 <= (2 * S[l] - l)$

对于一个 $r$ 而言,我们需要求出所有满足上述情况的 $l$ 中我们完成的区间数最多的那个然后转移过来。

由于 $2 * S[i] - i$ 的范围在 $[-n,n]$ 间,所以我们设置 $f[x]$ 表示所有满足2 * S[i] - i == x 的 $i$ 中分割出最多的区间。因此我们每次需要求解一个 r 的时候,我们只需要查询在区间 [ (2 * S[r] - r) + 1 , n]f[x]的最大值,然后我们在将 f[2 * S[r] - r] 设置为我们得到的值。

鉴于此,我们需要一个支持单点修改,区间查询的数据结构,那么我们用线段树完成此部分操作即可。

code

algorithm