A
题意：维护序列 \(a\)，支持单点修改。
每次找到满足 \((a_1 \oplus b) \le (a_2 \oplus b) \le \cdots \le (a_n \oplus b)\) 的最小非负整数 \(b\)；或判断无解。\(1\le n, q \le 10^6\)。
肯定是把大条件拆成 \(n - 1\) 个小条件，大条件成立当且仅当所有小条件成立。
- \(a_{i} = a_{i + 1}\)，随便怎么操作都满足条件。
- \(a_i < a_{i + 1}\)，不能操作从高到低第一个不同位，其他随便操作。
- \(a_i > a_{i + 1}\)，必须操作从高到低第一个不同位，其他随便操作。
随便记录次数维护一下，如果矛盾则无解。submission
B
题意：给定 \(n, a\)，求满足 \(p_i \in [\max(1, i - (n - a) + 1), \min(n, i + a - 1)]\) 的 \(n\) 阶排列个数，多测。
数据范围：\(1 \le n \le 10^6,\ a \le 200,\ a < n, T \le 10\)。
当限制条件全是 \([1, \min(n, i + a - 1)]\) 时很容易做：
前 \(n - a\) 个数范围为 \([1, i + a - 1]\)，每个数有 \((i + a - 1) - (i - 1) = a\) 种取法（减掉前 \(i - 1\) 个数用掉的）。
后 \(a\) 个数范围为 \([1, n]\)，即剩下 \(a\) 个数随意分配。此时方案数就等于 \(a^{n - a} \times a!\)。
回到原问题，\(i - (n - a) + 1 > 1\) 的就是后 \(a\) 个人。考虑容斥，钦定 \(a\) 个人中有 \(j\) 个属于 \([1, i - (n - a)]\)。
由于被钦定 \(j\) 个人取值范围一定包含于前 \(n - a\) 个人，因此前 \(n - a\) 个人每人有 \(a - j\) 种取法。
后 \(a\) 个人中没被钦定的可以随便选，\((a - j)!\) 种方案。
设 \(f(i, j)\) 表示 \(a = i\) 时钦定 \(j\) 个的方案数，如果 \(n - a + i\) 被钦定，可取的位置有 \(i\) 种，有 \(j - 1\) 个已经被用过。
根据 \(n - a + i\) 要不要钦定从 \(f(i - 1)\) 转移：\(f(i, j) = f(i - 1, j) + f(i - 1, j - 1) \times (i - j + 1)\)。
时间复杂度 \(O(a^2 + Ta\log n)\)。submission
C
题意：\(n\) 个城市，\(m\) 条单向铁路。\(i\) 号铁路依次经过 \(v_{i, 1}, v_{i, 2}, \cdots, v_{i, s_i}\)，其中 \(v_{i, j} \to v_{i, j + 1}\) 的铁路长度是 \(t_{i, j}\)
每条铁路可以在任意站上/下车。求一条 \(1\sim n\) 的最短路，并使相邻两个换乘点距离的平方和最大。