Codeforces Round 326 E, F

2016-09-08 | [Competitive programming]

E

非負整数列に対して，

• ある範囲の値すべてにある値 x を XOR する
• ある範囲の値から何個か選んで XOR して作れる値の個数を求める

というクエリを処理するという問題．

2 番目のクエリは，結局「ビットベクトルが張る Z/2Z 上の線形空間の次元を求めろ」という問題に帰着される． これは，変更クエリがなければ，Segment Tree の各ノードに「対応する範囲に含まれるベクトルたちの基底」を持たせることで比較的高速に答えられる．

a1, a2, …, an で張られるベクトル空間は，a1, (a1 xor a2), (a1 xor a3), …, (a1 xor an) で張られるベクトル空間であることに注意する． すると，a1 xor x, a2 xor x, …, an xor x で張られるベクトル空間は，a1 xor x, (a1 xor a2), (a1 xor a3), …, (a1 xor an) で張られるベクトル空間になる．

よって，単に基底を持つかわりに，x1 と「(x2, x3, …, xn) で張られるベクトル空間の基底」を持っておくと，変更クエリも効率よく処理できる． (伝播遅延の Segment Tree を用い，範囲全体更新の際には x1 部分だけを更新する)

F

文字列 s1, s2, …, sn が与えられるので，「si の sk 中での登場回数，の i = l, l+1, …, r での総和」を求めるクエリを処理する問題．

「s1, s2, …, sr が sk 中に登場する回数，の総和」が求められればよい．

文字列を適当なスペーサで挟んで長い文字列を作り，Suffix Array を求めておく． すると，各 si について，sk 中へ部分文字列として登場するときの現れは，Suffix Array 上ではある範囲になる．

s1, s2, …, sn と順に見ていき，適宜クエリを処理することにする． sk について答えを求めるときには，その各 suffix について，suffix の prefix として他の si が登場する回数が求められればよい． これは，sk が短ければSegment Tree を用いて適宜更新すると行える． sk が長いときは，文字列が登場したときに，各「長い文字列」の中に自分は何回現れるか，を計算し，それぞれ足し込む．

この閾値を適当に設定することで，十分高速に問題を解くことができる．