CF495 F. Sonya and Bitwise OR
コンテスト参加記録だけじゃなくて、過去問を解いた時も時々記事を書いていこうかなと思います。
自分用なので、解説というよりは考察・学習メモ。いつもよりは雑になります。
問題情報
リンク
問題概要
長さ の数列 と整数 が与えられる。以下のクエリ合計 個を処理せよ。
制約
- クエリ1について、 、
- クエリ2について、
考察
クエリ2を区間和問題に帰着
まず考えたこと。
- 区間に関する大量のクエリ。セグ木っぽい。
- ORは要素を足していくと単調増加するので、1クエリに 使っても良いならしゃくとりできる。でも今回はクエリが多いので間に合わない。
- 1クエリにかけていい時間が か くらいなので、区間和とかを使ってまとめて計算したい。
というところで、各インデックス ごとに「左端を とした区間で、条件を満たすものの個数」のような値を持っておき、BITやセグ木で区間和を取れないかと考えた。ただ、これだと少し扱いにくい。
これを少し修正し、単調性があることを利用して「左端を とした区間が条件を満たすときの、一番小さい右端の位置」とする。こうすると、そのような右端の位置は を増加させると単調増加していくので、扱いやすそう。
「左端を とした区間が条件を満たすときの、一番小さい右端の位置」を保持しておき、これを と表記する。これが求まっていると、クエリ 2 l r
に対する答えは以下のように求められる。
これなら、
- 二分探索は要素アクセスが であれば 。ただし がセグ木に乗っている場合は、単純にやると 。
- 区間和は 。
ということで、 であればなんとか通りそう。次は をどのように維持するかを考える。
クエリ1の処理
の初期値は、区間ORをセグ木に入れて二分探索をすると全要素 で求められる。最初にこれを計算しておく。
問題はクエリ1の処理。 の値が変更されると、もちろん の値も変わる可能性がある。より具体的には、クエリ 1 i y
に対して、
- を満たす位置 であって、
- 変更前の値 が を満たすもの
は、 の値が変わる可能性がある。( であるときは、 の値が変わっても は変化しない)
この条件を満たす全ての を見ていくのは非常に大変だが、ここでORの性質を思い出す。要素を追加していったとき、ORの値は「今までになかったビットが増えた」ときにしか増えない。
つまり を起点にして、左側に区間を広げるにしろ、右側に区間を広げるにしろ、「新しいビットが登場」するポイントでのみORの値が変わるため、そこだけを調べればよいことがわかる。
ということで、「要素 から見て、左側/右側それぞれ、一番近いところで 番目のビットが立っているのはどこか」が各ビット位置 について欲しくなる。もしこれが分かっていれば、
- 左端は から始めて、ビットが増える点ごとに左に伸ばしていく。
- それぞれの左端 に対して、右端をどこまで伸ばせばORの値が 以上になるかを調べる。このときも、ビットが新しく立つ点のみを調べれば良い。
- これで、ある左端 について が求まった。ここで、 から次にビットが増える直前まで左端を伸ばしても、右端の値は変わらないはずである。なので、区間に対して を同じ値で上書きすることができる。
というような更新が でできる。ここで は の最大ビット数であり、すなわち である。
ということで、「要素 から見て、左側/右側それぞれ、一番近いところで 番目のビットが立っているのはどこか」が必要になる。この値もクエリ1によって変動するが、区間更新できるようなデータ構造に乗せておけば更新は難しくない。
必要な道具の整理
ここまでの考察から、必要な道具を整理する。
まず、 の初期値を求めるために
が必要であり、これはセグメント木で可能である。そのほかに、
これらが必要である。
区間更新を行うには、遅延評価セグメント木を用いることができる。書いたことが無かったので、以下の記事を参考にしつつ、区間更新、区間和ができるものに修正した。(つたじぇーさんありがとうございます!)
遅延評価セグメント木をソラで書きたいあなたに - hogecoder
これで必要な道具が全部揃った。
ACコード
実行時間はギリギリだった。実装もなかなか重め。
余談
公式解法は違う解き方をしていて、遅延評価セグメント木を使っていない。何故か英語の解説がないが、親切な人がロシア語解説からの翻訳を書いてくれている。
感想
- OR演算の単調性をフル活用した。難しい問題だと、このレベルのテクは呼吸するように使うことが求められる。
- 「区間の数」の数え上げは愚直だと 以上かかり、これを工夫で や にすることはよくある。今回はそこからさらに落とすための発想が必要だった。
- 「答えを得るために必要な値は何か」「その値を得るために必要な値は何か」…というように、難しい問題でも段階的に考察を進めていくことができた。本番でもこれができるようになりたい。
- 遅延評価セグメント木を初めて使った。初めて使う道具で重い問題に挑むのは無謀。今回もかなりバグらせた。