E1. 切奥普斯与一场比赛（简单版本）详细题解

问题重述

有 $n$ 名参赛者，分成 $m=2$ 个城市（城市 $1$ 和城市 $2$）。每名参赛者 $i$ 具有力量 $a_i$、智慧 $b_i$（$b_i \ge a_i$）和专长 $s_i$。我们要构造至多 $5n$ 道题目，每道题有难度 $d$ 和主题 $t$（所有主题互不相同）。参赛者 $i$ 能解出一道题当且仅当：

• 力量条件：$a_i \ge d$，或
• 专长条件：$s_i = t$ 且 $b_i \ge d$。

要求：城市 $1$ 的每名参赛者解出的题目数量严格大于城市 $2$ 的每名参赛者解出的题目数量。求构造或输出 $-1$。

核心观察

由于主题必须互不相同，每个主题最多只能出一道题。因此，每个参赛者至多可以通过专长条件额外多解一道题（即主题与自己专长相同的题目），其余题目只能通过力量条件解决。

设我们构造的题目难度集合为 $D$（允许重复难度？实际上难度可以相同，但主题必须不同，所以难度可以重复）。对于参赛者 $i$，定义：

• 基础解题数 $base_i = |\{ d \in D \mid a_i \ge d \}|$（即力量条件能解的题数）。
• 额外解题数 $extra_i = 1$ 如果存在一道主题 $t = s_i$ 的题目且其难度 $d$ 满足 $a_i < d \le b_i$，否则 $0$。

总解题数 $solve_i = base_i + extra_i$。

我们的目标是：$\min_{i \in city1} solve_i > \max_{j \in city2} solve_j$。

构造思路

1. 控制基础解题数

基础解题数只取决于 $a_i$ 和难度集合 $D$。由于我们可以自由选择 $D$ 中的难度（任意整数），我们可以任意指定每个 $a_i$ 对应的基础解题数，只要满足单调性：若 $a_i < a_j$，则 $base_i \ge base_j$（因为更小的 $a$ 能解更多的题）。实际上，我们可以通过选择合适的难度阈值来精确控制基础解题数的分布。

一种简单有效的方法：将参赛者按 $a_i$ 降序排序，然后依次在每个不同的 $a$ 值处添加 两道 新题目，难度恰好等于该 $a$ 值（主题为新的未使用主题）。这样，对于所有 $a$ 值大于当前值的参赛者，基础解题数会增加 $2$；对于 $a$ 值等于当前值的参赛者，基础解题数也会增加 $2$（因为 $a_i \ge d$ 成立）。最终，基础解题数将完全由参赛者的 $a$ 值排名决定：$a$ 越大，基础解题数越小。

具体实现中，标程先对参赛者按 $a$ 降序排序，然后遍历每个不同的 $a$ 值，在每段连续相同 $a$ 值之后，添加两个新问题（难度为该 $a$ 值）。这样，所有 $a$ 值小于该值的参赛者（即更靠后的）基础解题数会少 $2$。

2. 专长题的安排

每个专长 $s$ 最多可以出一道题（主题 $=s$），其难度 $d_s$ 可以自由选择。该题会对所有满足 $s_i = s$ 且 $b_i \ge d_s > a_i$ 的参赛者额外贡献 $+1$。我们希望城市 $1$ 的参赛者尽可能多地获得额外分，城市 $2$ 的参赛者尽可能少地获得额外分。

为此，我们需要为每个专长 $s$ 选择一个合适的难度 $d_s$，使得：

• 对于城市 $1$ 中具有专长 $s$ 的参赛者，希望 $d_s$ 落在 $(a_i, b_i]$ 内，以便他们获得额外分。
• 对于城市 $2$ 中具有专长 $s$ 的参赛者，希望 $d_s$ 要么 $\le a_i$（此时他们本已通过力量条件解出该题，但基础分已算过，不会重复），要么 $> b_i$（则他们解不了）。注意，如果 $d_s \le a_i$，则该题已被基础分计入，不会额外增加；如果 $d_s > b_i$，则他们无法解；只有 $a_i < d_s \le b_i$ 才会额外增加。因此，我们应避免让城市 $2$ 的参赛者满足 $a_i < d_s \le b_i$。

此外，还有一些全局限制：由于基础解题数已经通过屏障题形成了阶梯，我们还需要确保添加专长题后，城市 $1$ 的最小解题数仍然大于城市 $2$ 的最大解题数。

3. 可行性条件

记城市 $1$ 的最小 $a$ 值为 $L_1$，最大 $a$ 值为 $R_1$；城市 $2$ 的最小 $a$ 值为 $L_2$，最大 $a$ 值为 $R_2$。由于基础解题数由 $a$ 的排序决定，如果 $R_1 \le L_2$，则城市 $1$ 中所有参赛者的 $a$ 都小于等于城市 $2$ 的某些参赛者，导致基础解题数可能不满足严格大于关系。实际上，必须满足 $R_1 > L_2$，否则无法通过基础题拉开差距。更进一步，标程中检查了区间 $[L_1+1, R_2]$ 是否有重叠等条件，但针对 $m=2$ 的情况，可以简化为：若存在某个城市 $1$ 的参赛者 $a$ 值大于等于某个城市 $2$ 的参赛者 $a$ 值，则基础解题数可能颠倒，需要通过专长题纠正。具体条件由标程中的 bad 区间合并处理。

4. 构造算法（标程实现）

1. 预处理：读入数据，记录每个参赛者的 $(a,b,s)$，以及每个城市包含的参赛者编号。
2. 计算每个城市的最小和最大 $a$：$min\_a[i], max\_a[i]$。
3. 生成“屏障”问题：
   • 将所有参赛者按 $a$ 降序排序。
   • 遍历排序后的数组，每当遇到新的 $a$ 值时（即连续一段相同 $a$ 值的末尾），就添加两个新问题，难度等于该 $a$ 值，主题使用新的、未出现过的整数（确保唯一）。
   • 这些屏障问题保证了基础解题数的阶梯性。
4. 处理专长题：
   • 对于每个专长 $s$，考虑所有城市 $1$ 中具有该专长的参赛者，记录他们的 $b$ 值的最小值（因为要尽可能让难度大但不超过 $b$，以便获得额外分）。这个值记作 $add[s]$。
   • 同时，对于城市 $2$ 中具有该专长的参赛者，他们会产生“禁止区间”：如果难度落在 $[L_1+1, b]$ 内（其中 $L_1$ 是城市 $1$ 的最小 $a$），则他们也会获得额外分，这是我们不希望的。因此，我们需要选择一个难度 $d_s$，使得 $d_s \le add[s]$，并且 $d_s$ 不落在任何城市 $2$ 的禁止区间内。标程通过二分或贪心，从 $add[s]$ 开始不断减小，直到避开所有禁止区间（包括之前由屏障题产生的全局禁止区间 bad）。
   • 最终得到一个可行的难度 $d_s$，并添加一道主题为 $s$、难度为 $d_s$ 的题目。
5. 验证：
   • 计算每个参赛者的实际解题数（基础部分通过二分查找难度列表得到，专长部分通过判断是否有自己的主题且难度在 $(a_i,b_i]$ 内）。
   • 检查城市 $1$ 的最小解题数是否严格大于城市 $2$ 的最大解题数。若是，输出构造；否则输出 $-1$。

复杂度

• 排序 $O(n \log n)$。
• 每个专长处理时，需合并禁止区间并二分查找，总复杂度 $O(n \log n)$。
• 最终验证 $O(n \log n)$。
• 满足 $n \le 3\cdot 10^5$ 的总和限制。

总结

本题的核心是构造性问题，通过控制基础题和专长题的难度，使得两个城市的解题数分布满足严格不等式。屏障题保证了基础部分的阶梯，专长题则用于微调，弥补可能存在的逆序。对于 $m=2$ 的简单版本，该构造总是可行的，除非某些特殊矛盾（如城市 $2$ 中某参赛者的 $b$ 值太小，无法避开禁区），此时输出 $-1$。标程提供了完整实现，按此思路即可通过。