T1

考场上咋都理不清楚，太钻牛角尖了。

先或再除和先除再或是一样的，相当于要构造一个序列 \(d\)，使 \(\sum \frac1{2^{d_i}}\ge1\)。求 \(\lfloor\frac{a_i}{2^{d_1}}\rfloor|\lfloor\frac{a_i}{2^{d_2}}\rfloor|\dots|\lfloor\frac{a_i}{2^{d_n}}\rfloor\) 的最小值。

考虑从高位到低位贪心确定答案。

答案初始成 \(2^w-1\)。维护一个序列 \(b\)，二进制下 \(b_i\) 的第 \(j\) 位为 \(1\) 当且仅当 \(a_i\) 右移 \(j\) 位再按位或上答案的值不等于答案。

显然，如果答案的第 \(j\) 位从 \(1\) 改成了 \(0\)，每一个 \(b_i\) 都应该或上 \(a_i\) 右移 \(j\) 位。每个 \(b_i\) 为 \(0\) 的最低位位数就是 \(d_i\) 最优取值。

T2

如果询问区间内有两个相同字符中间隔了一个，那么一定可行。否则判断是否有偶回文串覆盖。

考虑分治，对于每个分治区间 \([l,r]\)，\(mid=\lfloor\frac{l+r}2\rfloor\)，处理出每个 \([l,r]\) 中的位置跨越 \(mid\) 的连续回文覆盖的最小右端点（最大左端点），这个可以 PAM + dp 求。然后求解跨越 \(mid\) 的询问区间。

T3

首先明确只有二元环。将点转到平面上思考，\(A\) 国的每个城市建一个点 \((i,a_i)\)，对每个 \(B\) 国城市建一个点 \((b_i,i)\)，每个 \(A\) 国城市只能匹配右下方的 \(B\) 国城市，贪心 + set 解决。