CF495 F. Sonya and Bitwise OR

コンテスト参加記録だけじゃなくて、過去問を解いた時も時々記事を書いていこうかなと思います。

自分用なので、解説というよりは考察・学習メモ。いつもよりは雑になります。

問題情報

リンク

Problem - F - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ と整数 $x$ が与えられる。以下のクエリ合計 $m$ 個を処理せよ。

1 i y : $i$ 番目の要素 $a_{i}$ の値を $y$ に変更する。
2 l r : 区間 $\lbrack l, r \rbrack$ に含まれる部分区間 $\lbrack L, R \rbrack$ であって、その区間に含まれる要素 $a_{L}, ..., a_{R}$ のビットORを取ったものが $x$ 以上になるものの個数を出力する。

制約

$1 \le n, m \le 10^{5}$
$0 \le x, a_{i} \lt 2^{20}$
クエリ1について、 $1 \le i \le n$ 、 $0 \le y \lt 2^{20}$
クエリ2について、 $1 \le l \le r \le n$

考察

クエリ2を区間和問題に帰着

まず考えたこと。

区間に関する大量のクエリ。セグ木っぽい。
ORは要素を足していくと単調増加するので、1クエリに $O(n)$ 使っても良いならしゃくとりできる。でも今回はクエリが多いので間に合わない。
1クエリにかけていい時間が $O(1)$ か $O(\log n)$ くらいなので、区間和とかを使ってまとめて計算したい。

というところで、各インデックス $i$ ごとに「左端を $i$ とした区間で、条件を満たすものの個数」のような値を持っておき、BITやセグ木で区間和を取れないかと考えた。ただ、これだと少し扱いにくい。

これを少し修正し、単調性があることを利用して「左端を $i$ とした区間が条件を満たすときの、一番小さい右端の位置」とする。こうすると、そのような右端の位置は $i$ を増加させると単調増加していくので、扱いやすそう。

「左端を $i$ とした区間が条件を満たすときの、一番小さい右端の位置」を保持しておき、これを $b_{i}$ と表記する。これが求まっていると、クエリ 2 l r に対する答えは以下のように求められる。

$b_{i} \le r$ となる最大の $i$ を求める。 $b_{i}$ が $i$ について単調増加なので、これは二分探索できる。
以下の図のように、長方形の面積から $b_{i}$ の区間和を引き算することで、求めたい区間の数が求められる。

f:id:betrue12:20181011214713p:plain

これなら、

二分探索は要素アクセスが $O(1)$ であれば $O(\log n)$ 。ただし $b_{i}$ がセグ木に乗っている場合は、単純にやると $O((\log n)^{2})$ 。
区間和は $O(\log n)$ 。

ということで、 $O(m (\log n)^{2})$ であればなんとか通りそう。次は $b_{i}$ をどのように維持するかを考える。

クエリ1の処理

$b_{i}$ の初期値は、区間ORをセグ木に入れて二分探索をすると全要素 $O(n (\log n)^{2})$ で求められる。最初にこれを計算しておく。

問題はクエリ1の処理。 $a_{i}$ の値が変更されると、もちろん $b_{j}$ の値も変わる可能性がある。より具体的には、クエリ 1 i y に対して、

$j \le i$ を満たす位置 $j$ であって、
変更前の値 $b_{j}$ が $i \le b_{j}$ を満たすもの

は、 $b_{j}$ の値が変わる可能性がある。（ $b_{j} \lt i$ であるときは、 $a_{i}$ の値が変わっても $b_{j}$ は変化しない）

この条件を満たす全ての $j$ を見ていくのは非常に大変だが、ここでORの性質を思い出す。要素を追加していったとき、ORの値は「今までになかったビットが増えた」ときにしか増えない。

つまり $i$ を起点にして、左側に区間を広げるにしろ、右側に区間を広げるにしろ、「新しいビットが登場」するポイントでのみORの値が変わるため、そこだけを調べればよいことがわかる。

ということで、「要素 $i$ から見て、左側/右側それぞれ、一番近いところで $k$ 番目のビットが立っているのはどこか」が各ビット位置 $k$ について欲しくなる。もしこれが分かっていれば、

左端は $i$ から始めて、ビットが増える点ごとに左に伸ばしていく。
それぞれの左端 $j$ に対して、右端をどこまで伸ばせばORの値が $x$ 以上になるかを調べる。このときも、ビットが新しく立つ点のみを調べれば良い。
これで、ある左端 $j$ について $b_{j}$ が求まった。ここで、 $j$ から次にビットが増える直前まで左端を伸ばしても、右端の値は変わらないはずである。なので、区間に対して $b_{j}$ を同じ値で上書きすることができる。

というような更新が $O(B^{2})$ でできる。ここで $B$ は $a_{i}$ の最大ビット数であり、すなわち $B = 20$ である。

ということで、「要素 $i$ から見て、左側/右側それぞれ、一番近いところで $k$ 番目のビットが立っているのはどこか」が必要になる。この値もクエリ1によって変動するが、区間更新できるようなデータ構造に乗せておけば更新は難しくない。

必要な道具の整理

ここまでの考察から、必要な道具を整理する。

まず、 $b_{i}$ の初期値を求めるために

の初期値の区間ORの値
- 必要な操作：1点更新、区間OR

が必要であり、これはセグメント木で可能である。そのほかに、

要素から見て、左側/右側それぞれ、一番近いところで番目のビットが立っているのはどこか
- 必要な操作：区間更新、1点取得
左端をとした区間がクエリ2の条件を満たすときの、一番小さい右端の位置
- 必要な操作：区間更新、区間和

これらが必要である。

区間更新を行うには、遅延評価セグメント木を用いることができる。書いたことが無かったので、以下の記事を参考にしつつ、区間更新、区間和ができるものに修正した。（つたじぇーさんありがとうございます！）

遅延評価セグメント木をソラで書きたいあなたに - hogecoder

これで必要な道具が全部揃った。

ACコード

Codeforces

実行時間はギリギリだった。実装もなかなか重め。

余談

公式解法は違う解き方をしていて、遅延評価セグメント木を使っていない。何故か英語の解説がないが、親切な人がロシア語解説からの翻訳を書いてくれている。

感想

OR演算の単調性をフル活用した。難しい問題だと、このレベルのテクは呼吸するように使うことが求められる。
「区間の数」の数え上げは愚直だと $O(n^{2})$ 以上かかり、これを工夫で $O(n)$ や $O(n \log n)$ にすることはよくある。今回はそこからさらに落とすための発想が必要だった。
「答えを得るために必要な値は何か」「その値を得るために必要な値は何か」…というように、難しい問題でも段階的に考察を進めていくことができた。本番でもこれができるようになりたい。
遅延評価セグメント木を初めて使った。初めて使う道具で重い問題に挑むのは無謀。今回もかなりバグらせた。