Codeforces Round 917 (Div. 2)
内容提要
本文解析 Codeforces Round 917 Div.2 的四道题：A 题，若负数个数为偶数，将任一数变为 0 可使乘积最小；若为奇数则不变。B 题，统计不同首字母位置，累加可生成的不同字符串数。C 题，交替执行加一和清零操作，枚举前 2n 次求最大得分。D 题，用 01 字典树和归并排序计算数组逆序对数量。
延伸解读
A题：最小乘积的边界情况
A题要求通过将元素变为更接近0的值来最小化数组乘积。关键观察是负数的奇偶性：若负数个数为偶数，乘积为正，将任意元素变为0可使乘积为0，达到最小；若负数个数为奇数，乘积为负，保持不变即可。但需注意，如果数组中已有0，则无需操作。代码中通过异或判断负数奇偶，并检查0的存在，逻辑简洁。
B题：不同字符串数量的计数技巧
B题允许删除第一个或第二个字母，求最多能得到的不同字符串数。思路是考虑每个位置作为首字母的贡献：从后向前遍历，维护当前剩余字母的种类数，累加即可。因为删除操作可以保留任意后缀，所以每个位置能产生的不同字符串数等于当前剩余字母种类数。代码使用map计数，并在字母出现次数减为0时移除，确保种类数正确。
C题：操作策略与枚举上限
C题中，操作1使前缀加1，操作2计算得分并清零。由于操作2后数组清零，连续操作1最多使一个元素满足条件，因此交替操作1和2可稳定每两次得1分。但初始数组可能已有多个匹配，所以需枚举前2n次操作1后接操作2的情况，以获取最大得分。代码中枚举min(2n, d-1)次，并计算剩余操作可得的分数，取最大值。
D题：逆序对计算的组合方法
D题构建的数组由p和q生成，逆序对分为两部分：q数组内部的逆序对，以及不同p元素与q组合产生的逆序对。q内部逆序对用归并排序计算，乘以n。不同p元素间的逆序对通过01字典树处理，利用二进制位比较大小，并考虑q的排列特性，通过组合数学计算贡献。代码中字典树记录每个节点经过的数值及其剩余位数，遍历时动态移除并计算，最终累加取模。
Q&A
Codeforces Round 917 Div.2 的 A 题 Least Product 如何操作才能使数组乘积最小？
如果数组中负数的个数是偶数，则可以将任意一个数变为 0，使乘积为 0（最小）；如果负数的个数是奇数，则不需要操作，乘积已经为负。
B 题 Erase First or Second Letter 中，最多可以得到多少个不同的字符串？
最多不同字符串的数量等于所有不同首字母在字符串中首次出现位置之后（包括该位置）的后缀数量之和。具体算法：从后往前遍历，维护当前不同字符的集合大小，累加每个位置的不同字符数，并更新字符计数。
C 题 Watering an Array 中，为什么只需要枚举前 2n 次操作？
因为每次操作 2 后数组会被清零，而操作 1 会使前缀加一。通过分析可知，若先执行 x 次操作 1 再执行操作 2，最大得分约为 n - x/k；而交替执行操作 1 和 2 可稳定获得 x/2 分。当 x/2 < n - x/k 时，解得 x < 2n，因此只需考虑前 2n 次操作即可找到最优解。
D 题 Yet Another Inversions Problem 中，如何计算数组的逆序对数量？
逆序对分为两部分：一是 q 数组自身的逆序对，用归并排序计算；二是不同 p_i * 2^{q_j} 之间的逆序对，用 01 字典树处理。建树时记录每个节点经过的数值及其剩余比特位，遍历时动态移除并统计姐妹节点和结束节点的贡献，结合组合数学计算。
在 D 题中，01 字典树是如何用来统计逆序对的？
将每个 p_i 插入 01 字典树，记录每个节点上经过的数值及其剩余比特位长度。遍历 p 数组时，对于每个 p_i，从树中移除它，然后沿着其二进制位查询：对于每个节点，检查姐妹节点（相反位）上经过的数值，根据剩余比特位差计算能形成逆序对的数量；同时考虑当前节点结束的数值以及自身结束的情况。
C 题中，操作 1 和操作 2 分别是什么？
操作 1：对于所有 i ∈ [1, d_x]，将 a_i 增加 1。操作 2：计算 a_i = i 的数量并获得相应分数，然后将所有 a_i 重置为 0。
