読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるシフトセグメントツリー問題まとめ

シフトセグメントツリー

  • shifted segment tree(造語)
  • 一般的なセグメントツリーに全ての要素をシフトさせる機能を付けたもの
  • ルートとなる頂点を用意してそこを基準として更新や取得を行うというだけ
  • 傾向になるかもしれないのでまとめておく

簡単な解説

yukicoder No.151 セグメントフィッシング

https://yukicoder.me/submissions/168295
左右の魚は別々に管理しておき、1秒毎の魚の移動をシフトによって表現する。
あとは、枠外に出そうな魚は取り出して、方向を逆転させる。
シフトセグメントツリーが分かれば難しくない問題。

CodeChef Bear and Xor of Sums

https://www.codechef.com/viewsolution/13383491
公式Editorialに重要な公式がある。
https://discuss.codechef.com/questions/96502/xorsums-editorial

ある数xのb番目のビットが1である <=> x mod 2^(b+1) ≧ 2^b

あとは、xor計算は各ビット毎に独立で行えるため、各ビット毎に計算をしていけば良いのだが、この辺を工夫する必要がある。
連続する区間の総和の中で「x mod 2^(b+1) ≧ 2^b」となるxの数を数え上げる。この数が偶数ならそのビットは0, 奇数ならそのビットは1である。
あとは連続する区間の中で条件を満たすxの数を数え上げる方法を探せばよい。
[0,i]についてst[j] = 「x mod 2^(b+1) == j」を満たす区間和の数
とすると、[0,i+1]のstを計算するには、
1. stを右にA[i+1]分シフトする(現存の数に全て+A[i+1]する)
2. st[A[i+1]]をインクリメントする
これで、st[2^b, 2^(b+1)-1]の総和を取れば、[0,i+1]の数が得られる。
これを順番にやると答え。