いろはちゃんコンテスト Day1 L - をあぷろぶれむ

解法

初手は二分探索

この問題のように、

与えられた数列などから、列挙しきれない個数の要素（入力 $N$ 個に対して $O(N^{2})$ 個など）を計算する。それらをソートしたときの $K$ 番目の値を求めよ。

という形式の問題では、二分探索が有効なことが多いです。大きい方から $K$ 番目の値が $x$ であるときは $x$ 以上の要素が $K$ 個以上あり、「 $x$ 以上の要素が $K$ 個以上ある」という条件を満たす最大の $x$ が求める答えになります。

ということで「 $x$ を固定した時に、 $x$ 以上の要素が $K$ 個以上あるか？」というYes/No判定問題を考えます。

答えの範囲は $\min A_{i}$ から $A_{i}$ の全要素のOR値まであり得るので、全要素のOR値を $A_{all}$ と書くことにするとこの二分探索の反復回数は $O(\log A_{all})$ 回です。

数え方を効率的に

さて、 $x$ 以上の要素はどのようにすれば効率的に数えることが出来るでしょうか。

それぞれの要素は与えられた数列 $A_{i}$ の区間ORです。区間を伸ばす（ORに参加する要素を増やす）ことでORの値が減ることはないので、ある左端 $l$ を固定した時に区間ORが $x$ 以上になるような右端 $r$ の範囲には単調性があります。そのため、しゃくとり法を使うことができます。

全ての左端それぞれについて条件を満たす右端の境界を求め、区間の個数を数えます。このときの判定には「今見ている区間 $\lbrack l, r)$ について、その区間ORは $x$ 以上か？」という情報が必要になります。これを求める方法として2つ紹介します。

セグメント木、Sparse Tableを使う

これらのデータ構造を用いると区間ORを計算することができます。今回は更新クエリが必要ないためSparse Tableも使うことができます。

クエリの時間計算量はセグメント木が $O(\log N)$ 、Sparse Tableが $O(1)$ 。しゃくとり法が回るのに $O(N)$ 掛かるため、全体計算量は

セグメント木： $O(N \log N \log A_{all})$
Sparse Table：
- ※Sparse Table構築に $O(N\log N)$ かかるため

となります。記事末尾にACコードリンクを貼っていますが、セグメント木でもギリギリ間に合いました。

ビットごとに個数カウント

区間ORが計算できるデータ構造を持っていない…という場合にも解くことができます。

しゃくとり法で要素を区間に入れたり出したりする際には、上記のように区間の値を直接計算する他に、差分で更新する方法もよく使います。例えば区間和を扱っている場合は、要素を区間に入れる時に値を足し、区間から出す時には引けばよいです。

困ったことにOR演算の場合は、区間に入れる時には単にORで足せばよいのですが、引き算ができません。

ですが手段はあります。OR演算はビットごとに考えることができて、各ビットについて「区間内に $d$ ビット目が立っている要素が1個以上あれば、区間ORの $d$ ビット目は1である」ということが言えます。つまり「今区間内に $d$ ビット目が立っている要素がいくつあるか」をビットごとに管理しておけば、区間からの出し入れはこの値を増減させることで実現できます。そしてこの値が $0 \to 1$ または $1 \to 0$ と変化したときに区間ORの値を変化させればよいです。