D. Yet Another Inversions Problem
逆序对计数，有一点点思路但不多，猜到了可能有 \(\log\) 性质在，赛后看一眼题解果然是这样，但还是不耽误我做不出来qwq。。。
很容易想到将整个序列按序分成 \(n\) 个长度为 \(k\) 的子数组，因为每个子数组中的 \(p_{i}\) 是相同的，且不同子数组的 \(q_{i}\) 排布也相同。
考虑先对这 \(k\) 个子数组内部的逆序对计数，再将每个子数组中的所有数作为一个整体，对每一对不同子数组的逆序对计数，这利用了归并排序的原理。每个组内部计数很简单，我们主要考虑组间计数。
由于每个组内部已经计数过了，根据归并排序，在进行组间计数时，我们可以将每个组内先排序，这样会更方便计数且不会改变答案。
组间计数存在一些巧妙性质，这里直接放官解说明：
于是，对于 \(p\) 值分别为 \(p_{i},p_{j}\)（\(p_{i} < p_{j}\)） 的两个组，组间的逆序对数贡献的种类只有 $ \log_{2}\lfloor\frac{p_{j}}{p_{i}}\rfloor$ 种。而由于 \(p_{i},p_{j}\) \(\in [1, 3, ..., 2n-1]\)，因此这样的取值只有 \(O(\log n)\) 种。
显然现在我们有了 \(O(n^{2}\log n)\) 的暴力做法：枚举每一对 \((p_{i}, p_{j})\)，并计算 $ \log_{2}\lfloor\frac{p_{j}}{p_{i}}\rfloor$，以得出每个组对的逆序对贡献。考虑如何优化。
枚举每个 \(p_{j}\)，由上述，对于每一种逆序对数的贡献只有 \(O(\log n)\) 种，因此相应的每一种逆序对数的 \(p_{i}\) 取值就会对应 \(O(\log n)\) 个区间，开一个值域上的树状数组暴力统计即可。实现上要注意亿点点细节，具体实现见 code。
总复杂度 \(O(n\log^{2} n)\)。
code
E. Construct Matrix
一道出得挺不错的纯构造题，需要一些琐碎的分类讨论，关键点是需要先构造出 \(k \% 4 = 2\) 时的一个小子矩阵，使其成为关于同余类的偏量，将其填入矩阵然后尽可能地填充最容易想到的无影响的子矩阵（也就是 \(2 \times 2\)），进而完成在该同余类情况下整个矩阵的构造。感觉还是很吃对脑电波能力的qwq。。。
解法见官解即可，说得很明白。
code
F. Construct Tree
思维 + bitset 优化背包 dp，非常棒的一道题。
Q: 使用给定的 \(n\) 条边（每条边有固定的边权），问是否能构造一棵大小为 \(n + 1\) 的树，使得树的直径恰好为 \(d\)。
首先，对于树中的任意两条边，一定存在一条路径同时包含这两条边。因此如果最长的两条边的总长度超过了 \(d\)，就一定无解。
先将边长序列 \(l\) 排好序，考虑最大边权 \(l_{n}\)：如果存在一个边长子集，使得该子集的总和恰好为 \(d\)，且该子集可以包含 \(l_{n}\)，那么此时一定有解：我们可以先构造该子集组成的一条链，并将最大边长放在某一端，然后将剩下的所有边接在最大边长对应链中的内侧端点上，显然这样构造出的树的直径一定恰好为 \(d\)。这种情形可以 \(O(nd)\) 背包判断。
若不存在一个边长子集的总和恰好为 \(d\)，则显然无解；否则，就说明存在一个不能包含 \(l_{n}\) 的边长子集的总和恰好为 \(d\)。这时由这些边长构成的链可能会受到 \(l_{n}\) 的影响，使其无论如何也不会成为直径。 考虑如何判断是否存在这种影响：为尽可能地规避 \(l_{n}\) 对直径构造的干扰，我们应当尽量将这条直径放在这条链关于该链总长度的中点处，以防出现这条链的某个前缀/后缀加上 \(l_{n}\) 的大小超过 \(d\) 的情况。为此，我们需要对前缀与后缀长度分别开一维 \(dp\) 状态继续判断，若存在某一对前缀长度与后缀长度 \((pre, suf)\)（注意二者的交集为空），使得 \(pre + suf = d\) 并且 \(pre + l_{n} < d, suf + l_{n} < d\)，那么就有解：先拼好这条链，然后将其他包含但不限于 \(l_{n}\) 的边接到链中某个合适的结点上即可。显然此时 \(dp\) 的复杂度达到了 \(O(nd^{2})\)。观察朴素 dp 的过程：
dp2[0][0] = 1;for(int i = 1; i <= n - 1; i ++){for(int pre = d; pre >= 0; pre --){for(int suf = d; suf >= 0; suf --){if(pre >= l[i]) dp2[pre][suf] |= dp2[pre - l[i]][suf];if(suf >= l[i]) dp2[pre][suf] |= dp2[pre][suf - l[i]];}}}
很明显这是一个类型为 bool 的 dp，并且每次进行或运算时，关于某一维的偏移量是相同的。因此我们可以用 bitset 来优化掉其中一维的转移过程：
dp2[0][0] = 1;for(int i = 1; i <= n - 1; i ++){for(int j = d; j >= 0; j --){if(j + l[i] <= d){dp2[j + l[i]] |= dp2[j];}dp2[j] |= (dp2[j] << l[i]);}}
这两份代码是等价的，但是由于 bitset 空间压缩的特性，每一位只占一个 \(bit\) 而不是 \(w=64\) 个 \(bit\)，因此第二种写法的复杂度是 \(O(\frac{nd^{2}}{w})\) 的，\(n,d \leq 2000\)，小常数可以过。
code