APIO 2023 - B. Sequence
概要
Author: KoD
解法
$ xが中央値（の一つ）である区間について考える。区間を左右いずれかに長さ$ 1伸ばしても中央値が変化しないならば伸ばしてしまってもよいので、以下の$ 3通りのパターンのみ考えればよいことがわかる。
$ xは数列全体の中央値
区間の長さ$ nは偶数で、小さい方から$ n/2個の要素は全て$ x未満であり、小さい方から$ n/2 + 1番目の要素は$ x
区間の長さ$ nは偶数で、大きい方から$ n/2個の要素は全て$ xより大きく、大きい方から$ n/2 + 1番目の要素は$ x
一つ目の場合は自明。三つ目の場合は数列全体を$ -1倍すれば二つ目の場合に帰着されるので、以下では二つ目の場合のみ考える。
$ A_i < xなら$ B_i = -1, A_i \geq xなら$ B_i = 1とする$ (i = 0, 1, \dots, N-1)。$ C_i = \sum_{k=0}^{i-1}B_kとおくと、「小さい方から$ n/2個の要素は全て$ x未満であり、小さい方から$ n/2 + 1番目の要素は$ x」という条件を満たす区間は、$ C_l = C_rを満たす$ l, r \, (l < r)に対応する。
数列$ C の隣接する二要素の差は$ 1 なので、$ s, t が与えられたとき、$ l \leq s, t \leq r かつ$ C_l = C_r を満たす$ l, r が存在するための条件は二つの区間$ [\min_{i \leq s} C_i, \max_{i \leq s} C_i], [\min_{t \leq i} C_i, \max_{t \leq i} C_i] が共通部分を持つことである。
(累積和の最小値, 累積和の最大値, 総和) を持つセグメント木で数列$ Bを管理しておくと、$ s, tが与えらえたとき上記の判定が$ O(\log N)でできる。$ A_i = xとなる$ iを昇順に$ I_1, \dots, I_nとおくと、$ I_l, \dots, I_rを含む条件を満たす区間が存在するような$ l, rに対する$ r-l+1の最大値が求められればよく、これは尺取法を用いて解ける。
$ xの昇順に処理して$ Bを更新しつつ上記の問題を解くことで、全体で$ O(N \log N)で解くことができた。