Codeforces Round 1051 (Div. 2) 部分题解
D - Inversion Graph Coloring
理解成二分图，图中没有奇环，等价于序列不存在 \(i<j<k\) 使得 \(a_i>a_j>a_k\) 。
设 \(f_{i,x,y}\) 表示前 \(i\) 个数，当前序列最大值为 \(x\) ，下一个不能取小于 \(y\) 的数，可以认为 \(y\) 表示当前已经有了某 \(a_i>a_j\) 且 \(a_j\) 的最大值为 \(y\) 。
规定 \(x>y\) ，加入一个数 \(a_i\) 时，有转移（这里忽略掉第一维 \(i\)）：
这就有了 \(O(n^3)\) 的转移。
优化，第一个等价于对每个 \(y\) ，将 \(f_{*,y}\) 做前缀和给到 \(f_{a_i,y}\) ，第二个操作等价于对 \(f_{x,*}\) 做前缀和给到 \(f_{x,a_i}\) 。
\((x,y)\) 画在二维上，转化为对一个前缀做沿着 \(x\) 方向的前缀贡献，后缀做沿着 \(y\) 方向的前缀贡献。
用树状数组同时维护 \(f_{*,y}\) 和 \(f_{x,*}\) ，加速上面的贡献过程，最后对一些交接处，更新两个树状数组使得转移值的正确性（是 \(x=a_i\) 和 \(y=a_i\) 的位置）。
当然用树套树也可以。
趣事：上面的状态也可以理解为，用 Dilworth 转化成拆分成不多于两个非降序列，维护两个序列的末尾值。
E - Make Good
可以发现，若 \(s_i \not ={s_{i+2}}\) 则一定有操作交换 \(s_i,s_{i+2}\) ，并且相邻项交换几乎不可能。
若 \(s_i = s_{i+2}\) 则可能无法从操作上交换，但其实交换了整个序列不变，可以认为也是能交换的。
所以，奇偶分组后，奇偶相同的序列可以任意重排。
那么我们按奇偶分组，记录奇数位 ( 出现了 \(s_1\) ，偶数位 ) 出现了 \(s_2\) 。
我们要让 \(s_1+s_2=n/2\) ，由奇偶任意重拍，一定能进行若干操作使得 \(s_1,s_2\) 同时加 \(1\) 或 \(-1\) （剩余括号足够的情况下）：
得到 \(x=\frac{n/2-(s1+s2)}{2}\) ，这个值需要是整数，且要保证操作后 \(0\leq s_1+x \leq n/2,0\leq s_2+x \leq n/2\) ，若都满足，则这个 \(x\) 可行。
现在考虑构造，我们已经保证了恰好有 \(n/2\) 个 ( ，只需要让括号序列前缀和尽可能大，不会出现负数，那就把所有 ( 都排在最开始，再检查一遍是否可行就可以了。
F - Increasing Xor
加深了对线性基的理解
对于询问 \((l,r)\) ，\(a_i\) 可以被所有的 \(a_x,(l\leq x \leq i)\) 任意异或，这就想到线性基。
对于一个固定的 \(L\) ，从 \(L\) 往后的，由 \((L,i)\) 元素构成线性基最多只有 \(dim\) 个，对于固定的 \(L\) ，可以求出让线性基改变的 \(dim\) 个位置，按位置划分就构成了若干个区间。
我们对每个 \(L\) 求出其最远的 \(R_L\) 使得 \((L,R_L)\) 满足要求。
对于一个区间 \((l_i,r_i)\) ，我们知道当前的线性基，当前 \(L\) 最远位置的那个值 \(las\)，即最优构造下的最小的 \(a_{l_i-1}\) 。
那么我们查出 \(las\) 在当前线性基的排名 \(k\) （这里排名从 \(0\) 开始排，排名为 \(0\) 的数恒为 \(0\)），那么对于这个区间的构造可以依次取排名第 \(k+1,k+2,k+3,\cdots,k+r_i-l_i+1\) 的数，这里我们只需要找到排名 \(k+len\) 的数，继续递进到下一个区间即可。
如果 \(k+len\) 超出了线性基的表示范围，那最远右端点就要止步于当前区间，那只能步进 \(2^{cnt}-1-k\) 步。
具体对每个 \(L\) 求出 \(dim\) 个线性基位置可以用前缀线性基，记录线性基每一维下的最早出现时间。
一个小细节，求第 \(k\) 大需要用标准线性基，但前缀线性基由于要记录时间戳，不能标准化。这里我们维护一个新的标准线性基，对于固定 \(L\) 下，每进入一个区间求新线性基等于在这个线性基中加入一个数，可以在加入这个数时顺便把新的线性基标准化，复杂度就是 \(O(n \cdot dim^2)\) 的，查询复杂度 \(O(Q)\) ，已经把每个 \(R_L\) 求出来了。
代码
 部分题解)
)
)
安装mysql8.4.5(建议安装glibc2.28版本))
