D - Sequence Query Editorial by rsk0315
wavelet matrix で解けます。
wavelet matrix は、整数列 \(a = (a_0, a_1, \dots, a_{n-1})\) に関して
- 区間 \([l, r)\) のうちで \(x\) 以下のものの個数は?
- 区間 \([l, r)\) のうちで \(x\) 未満のものの個数は?
- 区間 \([l, r)\) のうちで \(x\) 以上のものの個数は?
- 区間 \([l, r)\) のうちで小さい方から \(k\) 番目の値は?
というクエリを \(O(\log(\max_i a_i))\) 時間で処理できます。
値の更新クエリは難しい(できなくはないが)ので、クエリを先読みし、追加クエリを全部処理したときの \(A\) を用意しておきます。 その上で、\([l, r) \gets [0, 0)\) で初期化しておきます。
便宜上、現在の \([l, r)\) において \(x\) 以下のものの個数を \(c_{\le x}\) と書きます。未満・以上についても同様に \(c_{\lt x}\), \(c_{\ge x}\) と書きます。
各クエリに対して以下のことをします。 クエリ 2, 3 の \(k\) は 0-indexed に変換しておきます(i.e. \(k\gets k-1\)) 。
- クエリ 1
- \(r \gets r+1\) で更新。
- クエリ 2
- \(c_{\le x} \le k\) であれば
-1
を出力。 - そうでなければ、小さい方から \((c_{\le x}-k-1)\) 番目の値を出力。
- \(c_{\le x} \le k\) であれば
- クエリ 3
- \(c_{\ge x} \le k\) であれば
-1
を出力。 - そうでなければ、小さい方から \((c_{\lt x} + k)\) 番目の値を出力。
- \(c_{\ge x} \le k\) であれば
座標圧縮したりしなかったりすることで、\(O(Q\log(x))\) 時間や \(O(Q\log(Q))\) 時間で解けます。
posted:
last update: