Codeforces Round #326 (Div.1) E. Duff as a Queen
問題概要
n 個の数からなる数列 {a_n} が与えられる．
また，q 個のクエリが投げられるものとする．クエリは以下の2種類．
ただし，以降は + を XOR, * を AND とする．
1. l <= i <= r なるすべての i に対して，a_i = a_i + k と更新．
2. a_l, ..., a_r からいくつか任意に選んで（全く選ばなくても良い），それらのすべての XOR を w とする．異なる w は何種類作れるか？
・制約
1 <= n <= 2 * 10^5
1 <= q <= 4 * 10^4
解法
全くわからなかったので教えてもらった．どうやら典型らしい．
まず，大前提として，二元体 F_2 上の (F_2)^n は線形空間をなす．
次に，a_l, ..., a_r に対し，c_l * a_l + ... + c_r * a_r (ここで，c_i は0または1である) 全体が作る集合は，これまた線形空間となっている．これを V_lr とおく．
さて，2種類目のクエリをどう処理するかを考える．
じつは，これは V_lr の次元を求めることと同じである．V_lr の基底を e_1, ..., e_k とする．
(because: 任意の w は 当然 V_lr の元である．よって，w = d_1 * e_1 + ... + d_k * e_k と「一意的に」表せる．一意性から，各 d_i の割り当てに対し，それぞれ1つの「異なる」 w が対応する．当然これが求めたいすべての w になる．各
d_i の割り当て方は2通りなので，全体として 2^k 通りの w が存在し，これが求める答えである．)
また，次元はたかだか32であることに注意する．（これは明らか）
さらに，1つ目のクエリをうまく処理しよう．
ここで，b_i := a_{i-1} + a_i とおく．この時，{a_l, b_{l+1}, ..., b_r} の基底は，{a_l, ..., a_r} の基底にもなっている．
(because: a_l + b_{l+1} = a_{l+1} であり，これを順番に繰り返せば，{a_l, ..., a_r} が生成できる．逆も当然可能．よって基底が一致する)
クエリ1が投げられたとき，この数列 b_n 上にどう影響するか考える．すると，実は区間の端だけ考えれば十分である事がわかる．なぜなら，区間の途中では，(a_i + k) + (a_{i+1} + k) = a_i + a_{i+1} となって相殺されるからである．
以上で得られたことをまとめる．
まず基底に関して，各区間における基底をセグメント木によって管理する方針が立つ．基底はたかだか32個しかないから，各ノードにすべての基底を保持しても問題ない．
基底のマージの仕方は，ガウスの消去法っぽくやる．すでに得られている基底に対して，別の基底の1要素 a を追加するとき，1が立っている最下位に注目する．
ただし，基底の任意の1要素 v に関して，v の1のビットの最下位では，v 以外の要素は 0 になっているものとする．（つまり，その位のビットを立てられるのは v のみ．）
各 v の最下位ビットを用いて a のビットをおろしていったとき，最終的に a が 0 でなければ，明らかに a は他の要素と直交しているので，新しい基底に含んで良い．
あとは，a の最下位の1のビットについて，先の基底の仮定を満たすように，各 v のビットをおろしていく（このとき，a は v の最下位の1ビットに影響しないことに注意）．
最後に a を追加する．この手順を繰り返せばOK．
・クエリ1について
{b_n} を考えるにしても，基底を考えるときに結局 {a_n} は必要なので，これはうまく求める必要がある．遅延セグメント木でも良さそうだが，実はBITで求められる．
最初に {a_n} の入力を取ったときに，BIT上の i 番目と i+1 番目に a_i を加えてやれば，sum(i) + sum(i-1) = a_i とできる．
あとは，
bit.add(l, k);
bit.add(r, k);
とすれば，sum(i) - sum(i-1) として k を xor したあとの a_i が得られる．
また，端に対応する b_i について，セグメント木のノードを更新する．
・クエリ2について
セグメント木上で [l+1, r) の区間の基底（つまり b_{l+1}, ..., b_r の基底）と，a_l を用いて，この区間の基底を求める．
基底のマージの仕方は先に述べた．
あとはこうして得られた基底から次元がわかるので，2^(次元) を出力すればよい．
ソースコード
長いので一部省略している．
#include <bits/stdc++.h> using namespace std; // segment_tree および fenwick_tree は省略 void binary_basis_insert(vector<int>& w, int a) { for(auto v : w) { if(v & (-v) & a) { a ^= v; } } if(a == 0) { return; } for(auto& v : w) { if(a & (-a) & v) { v ^= a; } } w.push_back(a); } vector<int> binary_basis(vector<int> const& w) { vector<int> res; for(auto v : w) { binary_basis_insert(res, v); } return res; } struct binary { using type = vector<int>; static type id() { return type(); } static type op(type l, type r) { if(l.size() < r.size()) { swap(l, r); } for(auto v : r) { binary_basis_insert(l, v); } return binary_basis(l); } }; int main() { int n, q; cin >> n >> q; vector<int> a(n); fenwick_tree<int> bit(n + 1); for(int i = 0; i < n; ++i) { cin >> a[i]; bit.add(i, a[i]); bit.add(i + 1, a[i]); } vector<int> b(n); for(int i = 1; i < n; ++i) { b[i] = a[i - 1] ^ a[i]; } vector<vector<int>> init(n); for(int i = 0; i < n; ++i) { init[i].push_back(b[i]); } segment_tree<binary> seg(init); for(int i = 0; i < q; ++i) { int t; cin >> t; if(t == 1) { int l, r, k; cin >> l >> r >> k; l--; bit.add(l, k); bit.add(r, k); seg.update(l, {bit.sum(l) ^ bit.sum(l - 1)}); if(r < n) { seg.update(r, {bit.sum(r) ^ bit.sum(r - 1)}); } } else { int l, r; cin >> l >> r; l--; auto res = seg.query(l + 1, r); binary_basis_insert(res, bit.sum(l)); cout << (1LL << res.size()) << endl; } } }
