ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

CF495 F. Sonya and Bitwise OR

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

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

問題情報

リンク

Problem - F - Codeforces

問題概要

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

  1. 1 i y :  i 番目の要素  a_{i} の値を  y に変更する。
  2. 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 に対する答えは以下のように求められる。

  1.  b_{i} \le r となる最大の  i を求める。 b_{i} i について単調増加なので、これは二分探索できる。
  2. 以下の図のように、長方形の面積から  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 について欲しくなる。もしこれが分かっていれば、

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

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

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

必要な道具の整理

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

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

  •  a_{i} の初期値の区間ORの値
    • 必要な操作:1点更新、区間OR

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

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

これらが必要である。

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

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

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

ACコード

Codeforces

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

余談

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

感想

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