感觉这题比 \(\rm F\) 难啊，\(\rm F\) 就是个板子，但为啥这题是蓝的，\(\rm F\) 是紫的。
思路
首先考虑 \(nq\) 怎么做。
发现很简单，按位贪心就行了。
具体地说，从大到小枚举二进制位，判断答案中能否出现这一位，若 \(i\) 当前这一位没有值，那么必须被补全到这个值，否则无所谓，然后拿当前代价和剩余能操作的次数比较即可。
然后考虑优化计算代价的过程。
先给出暴力计算代价的代码：
for (int s=20;~s;--s){
int g=1ll<<(s+1),re=0,gx=mx|(1ll<<s);
for (int i=1;i<=n;++i){
int t=a[i]%g;
if ((a[i]&mx)!=mx) re+=1ll<<s;
if ((a[i]&mx)==mx && (a[i]&gx)!=gx) re+=(1ll<<s)-t;
}
if (k>=re) k-=re,mx|=1ll<<s;
}
首先这个
if ((a[i]&mx)!=mx) re+=1ll<<s;
是很好优化的，高维前缀和即可。
考虑下面那个 \(\verb!if!\) 如何优化。
我们继续把它拆成
if ((a[i]&mx)==mx && (a[i]&gx)!=gx) re+=1ll<<s;
if ((a[i]&mx)==mx && (a[i]&gx)!=gx) re-=t;
上面那个柿子同样很好优化，仅需计算出是 \(\verb!mx!\) 的超集且不是 \(\verb!gx!\) 的超集的个数即可，同样可以高维前缀和。
至于下面那个柿子，我们考虑预处理一个数组 \(g_{p,s}\) 表示 \(s\) 所有超集的权值 \(\bmod\ 2^{p+1}\) 后的和，然后同样的道理，可以 \(\mathcal O(1)\) 算出结果。
这样这题就做完了，复杂度两只 \(\log\)。