解は Π_{0<=i

i<jとする。 (i, j)が満たしたい条件は A[i]+R[i]>=A[j]かつA[i]>=A[j]-L[j] jをループで固定する。jを昇順に見ていくならば A[i]+R[i]>=A[j]を満たすiはjが増加するごとに条件がきつくなる。 なのでi<jについて A[i]+R[i]の値を優先順位度付きキューで持っておいて、 A[i']+R[i']<A[j]となるような添え字i'を取り除いていく。 あとはA[i]>=A[j]-L[j]であるが、 取り除いたあとに残っているすべてのi</jについて></jとする。>

中央値がxの場合=>中央値がx以上の場合 f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二…