ぷの日記

作問・解説・日記など

The J-th Number (AOJ 2563) 解説

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 5 日目の記事です。

問題概要

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2563

$N$ 個の配列 $t_1,t_2,\ldots,t_n$ があります。初め、全ての配列は空です。

この配列に対して次の $M$ 個の操作を行いました。

・配列 $t_k (a_i \leqq k \leqq b_i)$ に対し、整数 $v$ を末尾に追加する。

以下の $Q$ 個のクエリを処理してください。

・配列 $t_k (x_i \leqq k \leqq y_i)$ に含まれる全ての要素を値が小さい順にソートした時、 $j_i$ 番目の要素を出力しなさい。

$1 \leqq N \leqq 10^9$

$1 \leqq M,Q \leqq 10^5$

$1 \leqq a_i,b_i,x_i,y_i \leqq N$

$1 \leqq v_i \leqq 10^9$

$1 \leqq j_i \leqq \sum_{k = x_i}^{y_i} |t_k|$

解法

クエリに対して、並列二分探索をします。

各クエリに対して、値 $mid$ 以下の数が配列 $t_{x_i}$ から $t_{y_i}$ の中に幾つ含まれるか知りたいです。

初めの $M$ 個の操作について追加する値、 $Q$ 個のクエリについて $mid$ で二つを合わせてソートすると、以下の問題に帰着されます。

数列 $A$ に対して、以下の $2$ 種類のいずれかを行うクエリを処理する。

・ $A_{a_i}$ から $A_{b_i}$ に $1$ を加算

・ $A_{x_i}$ から $A_{y_i}$ の値の総和を求める

これは遅延セグ木を用いると答えることができますが、今回は $N$ が大きいため、普通にやると TLE/MLE します。

必要なところだけ作る遅延セグ木を用いると AC できます。

(実際には必要なところだけ作る遅延セグ木でも TLE したので、必要なところだけ作るStarrySkyTreeを用いました)

実装例

judge.u-aizu.ac.jp

終わりに

多分殴ってます。別解が存在したら追記するかもしれません。

追記 : これ座圧遅延セグ木で良いですね、解散

必要なところだけ作る (遅延セグ木 / StarrySkyTree) についての記事も出すかもしれません。