CF2143F Increasing Xor
如果是全局查询，那么首先对每个位置 \(i\) 建出前 \(i\) 个元素的线性基，然后按照线性基有效元素个数分类分出 \(O(\log V)\) 类，每一类的线性基相同。对于每一类，假设前一类的最大值为 \(x\)，这一类要填的长度为 \(len\)，那么如果在这一类的线性基中 \(x\) 排名为 \(rk\)，那么在这一类中我们就选取排名为 \(rk+1\) 到 \(rk+len\) 之间的数，该类的末尾显然就是排名 \(rk+len\) 的数。而求线性基第 \(k\) 大和一个数 \(x\) 的排名都是基本操作，单次复杂度一个 log。
现在考虑区间查询，考虑前缀线性基，即每次插入一个数时保留时间戳靠后的数，然后将时间戳靠前的数往后插入。由于需要求有效元素个数，扫描线 \(l\) 删除出现时刻 \(<l\) 的数即可。总时间复杂度 \(O(n\log^2n)\)。
CF2144F Bracket Groups
显然如果有 () 那么必然无解。否则，发现分成 ((((((...)))))) 和 ()()()...()()() 两组时所有子串必然能归到至少一组里，由此可见答案至多为 2。现在考虑什么时候答案能是 1，也就是说构造一个合法括号串使得其不包含给出的若干个字符串为子串。考虑对给出的子串建 AC 自动机，并在自动机上 dp，转化为不能在自动机上经过某些给定的点，由于要满足合法，还得记一个括号串前缀和。总复杂度 \(O(nk^3)\)。
CF2147F Exchange Queries
感觉思维很混乱。等我贺个题解先。