感觉这题也没那么难阿，但是就是不会做。
注意到若记 \(g'(x,S)=\min_{T\subseteq S}(x\oplus \operatorname{xor}(T))\)，则 \(g(x\oplus y,S)=g(x,S)\oplus g'(y,S)\)。证明这一结论并不困难，但是想到这个对我来说感觉还是有点太难了。
于是我们用线段树维护 \(g(\oplus_{j=1}^ia_j,S)\)，每次线性基变化时暴力重构。这样我们获得了一个 \(\mathcal O(n\log^2 V+Q\log n\log V)\) 的做法，过不去。
\(\mathcal O(n\log^2 V)\) 的部分共有两处，均在重构时。具体而言，重构时要先算出每个 \(g(\oplus_{j=1}^i a_j,S)\)，再重新建树。前者的优化比较简单，实际上不难发现 \(g(x,S\cup \{y\})=\max(g(x,S),g'(y,S)\oplus g(x,S))\)。
对于后者，我的做法是设一个块长 \(B\)，将序列按 \(B\) 分块。对于每一个块我们统计块内每一位的出现次数，并对这些块建线段树。修改查询时整块在线段树上改，散块就暴力。那么我们建树部分的复杂度降到了 \(\mathcal O(\frac{n\log V}{B})\)，代价是修改的复杂度上升到了 \(\mathcal O(B\log V)\)，不过由于是乘在 \(Q\) 上的因此无所谓。重点在怎么统计块内每一位出现次数。一种比较简单的方法是将数分成 \(w\) 段并开 \(w\) 个大小为 \(V^{1/w}\) 的桶来表示每一段的情况，这样每次加入一个数只需要往 \(w\) 个桶中加入数。而当一个块内的数加完时就可以 \(\mathcal O(V^{1/w}\log V)\) 统计。这样总复杂度即为 \(\mathcal O(\frac{n}{B}(\log V + V^{1/w})\log V+nw\log V+Q\log V(B+\log n))\)。我取了 \(B=64,w=16\)，实际测试只跑了 1s。