CF Round#930 Div.1
A. Bitwise Operation Wizard
题意：已知\(n\)，有一个未知的\(n\)的排列\(p\)，可以交互查询\(p_{a} | p_{b}\)与\(p_{c} | p_{d}\)的大小关系，在\(3n\)次内找出任意一组答案\(x, y\)使得\(p_{x}
\oplus p_{y}\)最大。
题解：最后的异或没看到被坑惨了，题意玩一下，查询可以直接用来比大小，那么先找到最大值，一定存在一组答案是由最大值\(p_{x}\)参与的，另一个数要满足跟它二进制互补，但是查询只有或。第一次查询找到所有或起来最大的\(p_{y}\)集合，他们一定弥补了\(p_{x}\)二进制中所有的0，那么在其中找最小值就是不含有\(p_{x}\)中所有的1。
B. Pinball
题意：一个球在一个一维平面内滚动，每个位置表示球的滚动方向'>'或者'<'，滚动后这一位置会变化为反向，问从每个位置开始滚动需要多久才可以滚出去。
题解：手玩一下，球的运动路径就是沿着一个方向一直走，碰到反向前形成了一条反向的路径，反向后在另一个方向重复这个过程，实际上就是反向到球出发的距离和的两倍。因此，考虑一下球最后的落点，这个方向只会走一次，顺便维护一下左侧的'>'和右侧的'<'即可。
C. Pokémon Arena
题意：\(n\)个人打比赛，每个人有\(m\)维的属性和出场费\(c_{i}\)，任何一个人只要某一维不低于对手就可以战胜他，初始1号在擂台上，战胜他就可以替代他守擂，你可以花费等量的钱来为任意选手永久提升任意的属性，求最小花费的方案使得第\(n\)个人打上擂台。
题解：首先分析一下这个背景，可以得到两个结论：
- 永久属性提升可以视作一次性提升：考虑你通过比较一个提升过的属性来攻擂，那么直接提升属性到攻擂者一定不会更差
- 一位选手不会多次登台：既然可以看作一次性提升，那么如果出现选手两次攻擂，直接消除掉中间的过程答案一定更优
然后发现就可以去掉dp的后效性了，直接做一个dp：f[i]表示第i人守擂的最小花费。可以发现dp的转移是不定向的，那么直接建图跑最短路。进而发现这个图边集是爆炸的，每个状态都有\(nm\)个转移方式，那就要优化建图，直接拆点，把每个维度按照数值排序，只在相邻数值的点对间建边，那么就可以把边的数量压缩到\(nm\)级别，最后跑一个最短路得到f[n]。
D. Bitwise Paradox
题意：给定两个数组\(a,
b\)和一个常数\(v\)，定义一个子区间\([l, r]\)是好的，当满足\(b_{l} | ... | b_{r} \geq
v\)，定义区间得权值为\(max(a_{l}, ..,
a_{r})\)。支持两种操作，单点修改\(b\)，区间查询好的子区间的权值中的最小值。
题解：看着就很像线段树，但是很难决定区间去维护什么，遇事不决就直接维护答案，考虑如何合并两个线段上的节点。父节点的答案取子节点的最小值，再考虑跨区间的情况.
或操作从高位按位考虑，只考虑更高位是紧约束的情况，分情况讨论：
如果\(v\)这一位是0，那么跨区间如果取了1，低位再怎么取都没有约束了，直接按照取1带来的约束更新答案，如果跨区间取了0，相当于没有新的约束增加，继续枚举下一位。
如果\(v\)这一位是1，那么跨区间必须取1，更新约束继续。
幸好权值为\(a\)的区间最大值，因此取1带来的约束就是一次最大值的更新，不同位置的1带来的约束是互不影响的，可以按位独立考虑。那么如果要取1，如何能让跨区间的权值最小呢，那就是跨区间包含了左节点区间中最右侧的1，或者包含右节点区间中最左侧的1，那么额外维护一下这个信息就可以在\(O(logV)\)时间内合并两个区间了。这里\(a\)的区间最值需要用RMQ与处理一下，总复杂度为\(O(qlogNlogV)\)。