CSAcademy Round #42 (Div. 2 only) E. Xor Submatrix
問題概要
長さの配列
が与えられる。 このとき行列
を次のように定義する。
xor
このとき, 部分行列のxorの最大値を求める。
制約
解法
xorの性質に従って, 次の3つに場合分けをする。
1. 部分行列の縦と横の長さが偶数
2. 部分行列の縦の長さが偶数または横の長さが偶数
3. 部分行列の縦と横の長さが奇数
1. の場合, 各は偶数回現れるため、xorは0となる。
2. の場合, 縦の要素か横の要素のxorが0になるため、1方向にのみ求めればよい。
3. の場合, を固定するとその領域のxor値を高速にもとめることができる。
いま横方向と縦方向は独立に考えられることから、横のxorを固定してそのxorに対して最大になるような縦のxorを選びたい。
これを高速に行う方法としてbinary trieというデータ構造がある。
kazuma8128.hatenablog.com
binary trieを使うことで集合から
とのxorが最大になるような要素を答えるというクエリを高速に処理できる。
ここでの集合は縦のxorであるため、
で求めることができ、後半部分は
(Bは最大で29)で処理できるため間に合う。
