Codeforces Round 326 E, F

2016-09-08 | [programming] [algorithm]

E

非負整数列に対して,

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

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 が長いときは,文字列が登場したときに,各「長い文字列」の中に自分は何回現れるか,を計算し,それぞれ足し込む.

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