详细题解

问题理解

我们有 $n$ 个程序员，$m$ 条证词，每条证词 $(t, j, i)$ 表示程序员 $j$ 在时刻 $t$ 在办公室，并且当时除了他还有 $i$ 个人。
我们要找到最大的 $k$，使得前 $k$ 条证词可以同时成立。

关键点：

• 每个程序员有一个连续的在场区间 $[l, r]$（进入时间 $l$，离开时间 $r$）。
• 在时刻 $t$，总人数必须等于该时刻所有证词中提到的 $i+1$（如果该时刻有证词）。
• 证词按输入顺序给出，但 $t$ 值可能重复吗？题目说 $1 \le t \le m$，且更大的 $t$ 表示更晚的时刻，所以 $t$ 是唯一的。

整体思路

1. 二分答案
   我们二分可能的 $k$，检查前 $k$ 条证词是否一致。

2. 验证函数 check(r)

   • 根据前 $r$ 条证词，确定每个程序员的最早出现时间 man[j].l 和最晚出现时间 man[j].r。
   • 检查同一时刻的不同证词是否人数一致。
   • 按时间顺序模拟，维护当前在办公室的人数，确保符合证词要求。

数据结构与变量说明

struct node {
    int t, j, num;  // 证词：时刻，程序员编号，其他人数量
    int l, r;       // 该程序员的出现区间 [l, r]
};
node op[N];         // 证词数组
node man[N];        // 程序员数组，存其出现区间
int tim[N];         // tim[t] 表示时刻 t 的总人数（来自证词）
set<int> vc[N];     // vc[t] 表示在时刻 t 离开的程序员集合

验证函数 check(r) 步骤详解

1. 初始化与区间计算

for (int i = 1; i <= r; i++) {
    man[op[i].j].l = min(man[op[i].j].l, op[i].t);
    man[op[i].j].r = max(man[op[i].j].r, op[i].t);
    // 检查同一时刻证词人数是否一致
    if (tim[op[i].t] && op[i].num + 1 != tim[op[i].t])
        return false;
    tim[op[i].t] = op[i].num + 1;
}

这里 op[i].num + 1 是总人数（包括自己）。

2. 记录离开事件

for (int i = 1; i <= r; i++)
    vc[man[op[i].j].r].insert(op[i].j);

vc[t] 表示在时刻 $t$ 离开的程序员集合。

3. 排序与初始化指针

sort(man + 1, man + n + 1);  // 按 l 从小到大排序

id 指向下一个可能进入的程序员，wp 是有证词的程序员数量。

4. 时间轴模拟

for (int i = 1; i <= m; i++) {
    if (tim[i] == 0) continue;  // 该时刻无证词，跳过
    // 将 l <= i 的程序员加入办公室
    while (man[id].l <= i && id <= wp)
        id++, fix++;
    // fix: 当前确定在办公室的人数
    // move: 当前可调整的人数（已进入但可提前离开）
    // cb: 未安排的程序员数量
    ...
}

5. 人数调整逻辑

• 如果 fix > tim[i]，说明确定在办公室的人太多，需要让一部分人在 $i$ 时刻之前离开。
  这里代码通过减少 id 来模拟让某些人提前进入并离开。
• 如果 fix + move < tim[i]，需要从 cb（未安排的程序员）中拉人进来，或者推迟某些人的离开。

算法复杂度

• 二分：$O(\log m)$
• 每次验证：$O(m + n \log n)$（排序 + 模拟）
• 总复杂度：$O(z \cdot (m + n \log n) \log m)$，在 $n, m \le 10^5$ 时可接受。

样例分析

样例1
输入：

3 5
1 1 1
1 2 1
2 3 1
4 1 1
4 2 1

输出：4

解释：

• 前4条证词可能成立，例如：
  程序员1：时刻1~4
  程序员2：时刻1~2
  程序员3：时刻2
  时刻1：1和2在 → 人数2 ✓
  时刻2：1、2、3在 → 人数3（但程序员3说除他外有1人，即总人数2）❌
  这里需要仔细安排区间使时刻2人数为2，例如程序员2在时刻1后离开，程序员3在时刻2进入并立即离开。

实际上，代码通过贪心调整实现了这种安排。

学习要点

1. 二分答案框架：当求“最大可行前缀”时，二分 $k$ 并验证。
2. 区间约束：每个程序员的出现区间由证词中的最早和最晚时刻确定。
3. 时间轴模拟：按时间处理事件（进入、离开），维护当前人数。
4. 贪心调整：用 fix（确定人数）和 move（可调整人数）来满足人数要求。
5. 复杂度控制：避免暴力枚举，利用排序和指针扫描。