Solution. LG10199 [湖北省选模拟 2024] 时与风 / wind

Description

给定 $n$ 个点 $m$ 条边的有向图，第 $i$ 条边有开放时间 $[O_i,C_i]$ 和到达时间 $[L_i,R_i]$，可以经过相邻的两条边 $i,j$ 当且仅当 $[L_i,R_i]\subseteq [O_j,C_j]$，给定起点 $S$，第一条边不受限制，求哪些边可达。

$1\le n,m\le 5\times10^5,1\le O_i\le C_i\le 10^9,1\le L_i\le R_i\le 10^9,{\color{yellow}1\le O_i,L_i\le 20}$

Solution

题目询问我们边上的可达性，这个通过 dfs 或 bfs 即可解决。

难点在于，每次从某条边到达一个点 $u$，我们希望找出可行的下一条边，这需要做一个二维偏序，看起来并没有什么好的解决方案。如果遍历 $u$ 所有的出边，复杂度将达到 $O(m^2)$。如果你注意到了本题的关键性质 $1\le O_i,L_i\le 20$，很自然的会想到枚举可行的左端点，现在只需要解决 $C\ge R$。我们对 $u$ 的所有出边按照 $O$ 放进桶里，分别按 $C$ 排序，查询时从尾部弹出满足 $C\ge R$ 的边即可。每条边只会访问一次，总复杂度 $O(m\log m+\max\{O_i,L_i\}\cdot m)$。

问题来了，如果你像我一样在考场上没有看到 $1\le O_i,L_i\le 20$ 这一关键性质，这题还能做吗？

其实仍然可以，做法和 CF198E Gripping Story 基本一致。

二维偏序是困难的，本题中搜索的优秀性质在于每个元素只需要访问一次，我们只要能快速定位到满足条件的元素并将其删除即可。具体来说，我们可以将之前提到的做法中的桶换成线段树，将出边按照 $O$ 放到线段树的叶子上，此外，线段树上的每个结点维护区间内所有出边 $C$ 的最大值，查询时根据最大值判断区间内是否存在可行的出边，若有则递归下去找到出边并更新信息，若没有则退出该结点。

我们仍然保证了每条边仅被访问一次，找到一条出边的代价是 $O(\log m)$（不离散化用动态开点则是 $O(\log V)$），总复杂度是优秀的 $O(m\log m)$。

Code

考场代码，实现的是后面这种方法。

namespace Main{
    const int N = 500005;
    int n, m, s, u[N], v[N], o[N], c[N], l[N], r[N];
    bool vis[N];
    vector<int> num[N], e[N], in[N];
    struct segtree{
        struct segtree_node{
            int l, r, mx;
        };
        vector<segtree_node> t;
        vector<vector<int>> buc;
#define ls p << 1
#define rs p << 1 | 1
        void resize(int siz){
            t.resize(4 * siz), buc.resize(siz);
        }
        void pushup(int p){
            t[p].mx = max(t[ls].mx, t[rs].mx);
        }
        void build(int p, int l, int r){
            t[p].l = l, t[p].r = r;
            if(l == r) { t[p].mx = buc[l].empty() ? 0 : c[buc[l].back()]; return; }
            int mid = l + r >> 1;
            build(ls, l, mid), build(rs, mid + 1, r);
            pushup(p);
        }
        void query(int p, int l, int r, int lim, vector<int> &res){
            if(t[p].mx < lim) return;
            if(t[p].l == t[p].r){
                int id = t[p].l;
                while(!buc[id].empty() && c[buc[id].back()] >= lim){
                    res.push_back(buc[id].back());
                    buc[id].pop_back();
                }
                t[p].mx = buc[id].empty() ? 0 : c[buc[id].back()];
                return;
            }
            int mid = t[p].l + t[p].r >> 1;
            if(mid >= l) query(ls, l, r, lim, res);
            if(mid < r) query(rs, l, r, lim, res);
            pushup(p);
        }
#undef ls
#undef rs
    }tree[N];
    void dfs(int p){
        vis[p] = true;
        vector<int> out;
        if(!tree[v[p]].t.empty()){
            int tmp = upper_bound(num[v[p]].begin(), num[v[p]].end(), l[p]) - num[v[p]].begin() - 1;
            if(tmp >= 0) tree[v[p]].query(1, 0, tmp, r[p], out);
        }
        for(int to: out) dfs(to);
    } 
    void Main(){
        input(n, m, s);
        for(int i = 1; i <= m; i++){
            input(u[i], v[i], o[i], c[i], l[i], r[i]);
            e[u[i]].push_back(i);
            num[u[i]].push_back(o[i]);
            in[v[i]].push_back(i);
        }
        for(int i = 1; i <= n; i++){
            if(num[i].empty() || i == s) continue;
            sort(num[i].begin(), num[i].end());
            num[i].erase(unique(num[i].begin(), num[i].end()), num[i].end());
            tree[i].resize(num[i].size());
            for(int j: e[i]){
                int p = lower_bound(num[i].begin(), num[i].end(), o[j]) - num[i].begin();
                tree[i].buc[p].push_back(j);
            }
            for(int j = 0; j < num[i].size(); j++){
                sort(tree[i].buc[j].begin(), tree[i].buc[j].end(), [](int x, int y){
                    return c[x] < c[y];
                });
            }
            tree[i].build(1, 0, num[i].size() - 1);
        }
        for(int st: e[s]) dfs(st);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(i == s) continue;
            int tim = 2e9;
            for(int x: in[i]) if(vis[x]) tim = min(tim, r[x]);
            if(tim == 2e9) tim = 0;
            // cerr << i << ' ' << tim << endl;
            ans = max(ans, tim);
        }
        write(ans);
        return;
    }
} // namespace Main

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。