Twelve Monkeys：時光穿梭路徑計數與 Multiset 解法

問題建模

n 個年份節點，m 條時光穿梭路徑 (x→y, x≥y)。q 次詢問：在第 p 年時，有多少年份可通過至少兩條不同路徑到達？

逆向思維 + Multiset

1. 從後往前處理詢問（年份大的先處理）
2. 維护 multiset 存儲所有可到達的目標年份
3. 當前年份 t，插入所有起點 ≥ t 的路徑終點
4. 若 multiset 中至少有 2 個元素 ≥ t，則 t 有解
5. 答案 = t - 第二小的可到達年份

核心代碼

multiset S;
sort(edges, edges+m, [](a,b){return a.u < b.u;});
sort(queries, queries+q, [](a,b){return a.d < b.d;});

int pos = m-1;
for (int i = q-1; i >= 0; i--) {
    int day = queries[i].d;
    while (pos >= 0 && edges[pos].u >= day) {
        S.insert(edges[pos].v);
        pos--;
    }
    int cnt = 0, vals[2];
    for (auto it = S.begin(); it != S.end() && cnt < 2; ++it) {
        vals[cnt++] = *it;
    }
    ans[queries[i].id] = (cnt >= 2 && vals[1] <= day) ? day - vals[1] : 0;
}

樣例解析

輸入：
9 3 3
9 1
6 1
4 1
6
7
2

輸出：
5
0
1

解釋：年份 6 可通過 6→1 和 6→7→8→9→1 兩條路徑到達 1、2

複雜度

O((m+q) log m)，multiset 操作 log 級，適合 50000 規模。