E2. 切奥普斯与一场比赛（困难版本）详细题解

问题重述

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

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

要求：对于所有 $1 \le i < j \le m$，城市 $i$ 的每一名参赛者解出的题目数严格大于城市 $j$ 的每一名参赛者解出的题目数。求构造或判断不可能。

---

核心思路

与简单版本类似，我们将解题数分为两部分：

• 基础部分：所有参赛者都能通过力量条件解出的题目（由难度 $\le a_i$ 的题目构成）。
• 额外部分：每个专长最多有一道题，参赛者若满足 $s_i = t$ 且 $a_i < d \le b_i$，则额外多解一道。

通过控制基础题的分布，我们可以让不同城市的参赛者获得阶梯状的基础解题数。然后，通过为每个专长选择恰当的难度，给某些参赛者（通常是城市编号较小的）增加一道题，从而微调，使得严格不等式成立。

---

关键定义

对每个城市 $p$，定义：

• $L_p = \min\{ a_i \mid i \in \text{city } p \}$（该城市的最小力量）
• $R_p = \max\{ a_i \mid i \in \text{city } p \}$（该城市的最大力量）

显然 $L_p \le R_p$。

---

可行性必要条件

对于相邻城市 $p$ 和 $p+1$，若 $L_p < R_{p+1}$，则区间 $(L_p, R_{p+1}]$ 内的难度会导致基础解题数的交错，必须通过额外题纠正。更精确地，定义禁止区间：

$$\text{bad}_p = [L_p+1,\; R_{p+1}] \quad \text{如果 } L_p < R_{p+1} $$

这些区间的并集记作 $\text{Bad}$，它们合并成若干个不相交的区间。任何难度落在 $\text{Bad}$ 内的题目都会使城市 $p$ 中力量为 $R_{p+1}$ 的参赛者与城市 $p+1$ 中力量为 $L_p+1$ 的参赛者之间的基础解题数差距缩小，导致难以满足严格不等式。因此，我们最终选择的额外题难度必须避开 $\text{Bad}$。

---

构造步骤

1. 生成“屏障”题目（控制基础解题数）

将所有参赛者按力量 $a_i$ 降序排序。遍历排序后的序列，每当遇到一个新的 $a$ 值时（即连续相同 $a$ 值的末尾），检查此时已处理的参赛者集合（即 $a$ 更大的那些）是否全部来自一个连续的编号区间（从某个城市到另一个城市）。具体条件：设当前已处理的参赛者中城市编号的最大值为 $M_1$，未处理的参赛者中城市编号的最小值为 $M_2$，若 $M_1 \le M_2$，则说明我们可以通过添加两道新题目（难度等于当前的 $a$）来“切断”前后两组，使后面的参赛者基础解题数减少 $2$。重复此过程，每次添加两个新题目，主题使用未出现过的大整数。

这一步结束后，我们得到了若干道屏障题，它们保证了：对于任意 $a$ 值，所有力量大于 $a$ 的参赛者比所有力量小于 $a$ 的参赛者多解 $2k$ 道题（其中 $k$ 是屏障题中难度大于 $a$ 的数量）。因此，基础解题数实际上只取决于参赛者的力量排名，并且相邻力量等级之间至少相差 $2$。

2. 确定每个专长对应的额外题难度

对于每个专长 $s$，考虑所有满足以下条件的参赛者：

• 来自某个城市 $p$，且 $a_i \le R_{p+1}$（即该参赛者的力量小于等于下一城市的最大力量）。这样的参赛者若获得专长题，可以帮助他们增加一道题，从而弥补与下一城市的差距。

我们对每个这样的专长 $s$，记录其可用的最大难度：$add[s] = \min\{ b_i \mid \text{参赛者 } i \text{ 满足 } s_i = s \text{ 且 } a_i \le R_{p+1} \}$（即这些参赛者中智慧的最小值）。然后，我们还需要排除一些禁止区间：

• 全局禁止区间 $\text{Bad}$（由相邻城市的力量区间产生）。
• 每个专长 $s$ 还有额外的禁止区间，来自城市 $p+1$ 中具有该专长的参赛者：对于每个这样的参赛者 $j$（$s_j = s$ 且 $a_j \ge L_p$），会产生禁止区间 $[L_p+1,\; b_j]$，因为如果难度落在此区间内，城市 $p+1$ 的这个参赛者也会额外解出该题，从而破坏不等式。

我们将这些禁止区间合并，然后从 $add[s]$ 开始，不断减小难度值，直到它不属于任何禁止区间（包括 $\text{Bad}$ 和专长自己的禁止区间）。最终得到的难度 $d_s$ 就是该专长题的难度。若无法找到（即 $d_s$ 减到 $0$ 以下），则该专长不能出题，但题目保证可行时不会发生。

3. 验证构造

将所有屏障题和专长题合并，得到题目列表。计算每个参赛者的实际解题数：

• 基础解题数 = 难度 $\le a_i$ 的屏障题数量（屏障题难度取自不同 $a$ 值，且按排序后很容易用二分计算）。
• 额外解题数 = 1 如果存在专长题且其难度在 $(a_i, b_i]$ 内，否则 0。 然后，对每个城市计算该城市参赛者的最小解题数和最大解题数。检查是否对于每个相邻城市 $p < p+1$，有 $\min\_solved[p] > \max\_solved[p+1]$。若成立，输出构造；否则输出 $-1$。

---

复杂度分析

• 排序 $O(n \log n)$。
• 处理屏障题时，使用 multiset 维护已处理城市的集合，每个参赛者进出一次，$O(n \log n)$。
• 对每个专长，合并禁止区间 $O(k \log k)$，其中 $k$ 是该专长涉及的参赛者数，总和 $O(n \log n)$。
• 最终验证 $O(n \log n)$。
• 总复杂度 $O(n \log n)$，满足 $n \le 3\cdot 10^5$ 的总和限制。

---

参考代码

（标程已提供，即为通用版本）

/**
 *    author:  tourist
 *    created: 01.12.2024 18:36:51
**/
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n), c(n);
    set<int> s;
    for (int i = 0; i < n; i++) {
      cin >> a[i] >> b[i] >> c[i];
      s.insert(c[i]);
    }
    vector<vector<int>> vs(m);
    for (int i = 0; i < m; i++) {
      int foo;
      cin >> foo;
      vs[i].resize(foo);
      for (int j = 0; j < foo; j++) {
        cin >> vs[i][j];
        --vs[i][j];
      }
    }
    const int inf = int(1.01e9);
    vector<int> min_a(m, inf);
    vector<int> max_a(m, -1);
    for (int i = 0; i < m; i++) {
      for (int j : vs[i]) {
        min_a[i] = min(min_a[i], a[j]);
        max_a[i] = max(max_a[i], a[j]);
      }
    }
    auto Unify = [&](vector<pair<int, int>>& bad) {
      sort(bad.begin(), bad.end());
      int ptr = 0;
      for (int i = 1; i < int(bad.size()); i++) {
        if (bad[i].first <= bad[ptr].second + 1) {
          bad[ptr].second = max(bad[ptr].second, bad[i].second);
        } else {
          bad[++ptr] = bad[i];
        }
      }
      bad.resize(ptr + 1);
    };
    vector<pair<int, int>> bad;
    for (int id = 0; id < m - 1; id++) {
      if (min_a[id] < max_a[id + 1]) {
        bad.emplace_back(min_a[id] + 1, max_a[id + 1]);
      }
    }
    Unify(bad);
    vector<int> ctr(n);
    for (int i = 0; i < m; i++) {
      for (int x : vs[i]) {
        ctr[x] = i;
      }
    }
    vector<pair<int, int>> tasks;
    int unused = 0;
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return a[i] > a[j];
    });
    multiset<int> before, after;
    for (int i = 0; i < n; i++) {
      after.insert(ctr[i]);
    }
    {
      int beg = 0;
      while (beg < n) {
        int end = beg;
        while (end + 1 < n && a[order[end + 1]] == a[order[end]]) {
          end += 1;
        }
        for (int i = beg; i <= end; i++) {
          before.insert(ctr[order[i]]);
          after.erase(after.find(ctr[order[i]]));
        }
        if (!before.empty() && !after.empty() && *prev(before.end()) <= *after.begin()) {
          for (int i = 0; i < 2; i++) {
            do {
              unused += 1;
            } while (s.find(unused) != s.end());
            tasks.emplace_back(a[order[end]], unused);
          }
        }
        beg = end + 1;
      }
    }
    map<int, int> add;
    for (int id = 0; id < m - 1; id++) {
      for (int i : vs[id]) {
        if (a[i] <= max_a[id + 1]) {
          if (add.find(c[i]) == add.end()) {
            add[c[i]] = b[i];
          } else {
            add[c[i]] = min(add[c[i]], b[i]);
          }
        }
      }
    }
    map<int, vector<pair<int, int>>> kill;
    for (int id = 1; id < m; id++) {
      for (int i : vs[id]) {
        if (a[i] >= min_a[id - 1]) {
          kill[c[i]].push_back({min_a[id - 1] + 1, b[i]});
        }
      }
    }
    for (auto& [type, x] : add) {
      auto& k = kill[type];
      Unify(k);
      int dif = x;
      while (true) {
        bool changed = false;
        {
          auto it = lower_bound(bad.begin(), bad.end(), make_pair(dif + 1, -1));
          if (it != bad.begin()) {
            it = prev(it);
            if (it->second >= dif) {
              dif = it->first - 1;
              changed = true;
            }
          }
        }
        {
          auto it = lower_bound(k.begin(), k.end(), make_pair(dif + 1, -1));
          if (it != k.begin()) {
            it = prev(it);
            if (it->second >= dif) {
              dif = it->first - 1;
              changed = true;
            }
          }
        }
        if (!changed) {
          break;
        }
      }
      tasks.emplace_back(dif, type);
    }
    vector<int> all;
    map<int, int> spec;
    for (auto& [x, y] : tasks) {
      all.push_back(x);
      spec[y] = x;
    }
    sort(all.begin(), all.end());
    vector<int> solved(n);
    for (int i = 0; i < n; i++) {
      solved[i] = upper_bound(all.begin(), all.end(), a[i]) - all.begin();
      if (spec.count(c[i]) && spec[c[i]] > a[i] && spec[c[i]] <= b[i]) {
        solved[i] += 1;
      }
    }
    vector<int> min_solved(m, inf), max_solved(m, -1);
    for (int i = 0; i < m; i++) {
      for (int j : vs[i]) {
        min_solved[i] = min(min_solved[i], solved[j]);
        max_solved[i] = max(max_solved[i], solved[j]);
      }
    }
    bool win = true;
    for (int id = 0; id < m - 1; id++) {
      if (min_solved[id] <= max_solved[id + 1]) {
        win = false;
        break;
      }
    }
    if (win) {
      cout << tasks.size() << '\n';
      for (auto& [x, y] : tasks) cout << x << " " << y << '\n';
    } else {
      cout << -1 << '\n';
    }
  }
  return 0;
}

---

总结

本题的困难版本要求处理任意多个城市，核心依然是利用屏障题建立基础解题数的阶梯，再通过为每个专长选择合适难度的题目进行微调。全局禁止区间 bad 和每个专长自己的禁止区间 kill 共同限制了额外题的难度选择。标程通过合并区间和贪心下降难度，保证了在可行的情况下能够构造出满足条件的题目集合。最终验证确保了构造的正确性。