题解：P14372 [JOISC 2018] 比太郎的聚会 / Bitaro's Party

· · 题解

由于 S_i < E_i，所以说这是一张拓扑序为 1 \sim N 的 DAG，那么就不用跑拓扑排序了。设 f_x 为以 x 为终点，所有空闲点里面到终点距离的最大值，有转移方程：

f_x = \max_{y \in \text{pre}(x)} \{ f_y \} + 1.

这样太慢了。由于 \sum Y_i \le 10^5，考虑根号分治。对于 Y_i \ge B 的部分跑上述 dp，对于 Y_i < B 的部分，我们提前预处理出 S_x 表示终点为 x，到 x 的距离前 B 大的点集，每次询问的时候直接在里面找就行了。

void merge(int y, int x) {
    // merge y, x + 1
    std::vector<pii> fin, t = ok[x];
    std::vector<int> u;
    for (auto& [a, b] : t) a += 1;
#define try(x) if (!vis[x.se]) { \
    vis[x.se] = 1, fin.eb(x), u.eb(x.se); \
    }
    int i = 0, j = 0;
    while (i < sz(ok[y]) && j < sz(t) && sz(fin) < B) {
        if (ok[y][i] <= t[j]) {try(t[j]); ++j;}
        else {try(ok[y][i]); ++i;}
    }
    while (i < sz(ok[y]) && sz(fin) < B) {
        try(ok[y][i]); ++i;
    }
    while (j < sz(t) && sz(fin) < B) {
        try(t[j]); ++j;
    }
    ok[y].swap(fin);
    for (auto& v : u) vis[v] = 0;
}

for (int i = 1; i <= n; ++i) { 
    for (auto& y : adj[i]) merge(i, y);
    if (sz(ok[i]) < B) ok[i].eb(0, i);
}

时间复杂度 \mathcal O((N + M + Q)B + (N + M) \times \frac{V}{B})，空间复杂度 \mathcal O(NB + M)。我建议 B 取 100 \sim 128 的样子，因为取到 \sqrt n 会 MLE。