JOISC2014A 题解

sinsop90 · 2023-10-28 12:32:10 · 题解

模拟赛 T1，结果写错两个字符，还过了大样例，绑包后直接 0 分起飞。

注意到很好的性质是你从 1 走到 n 的 X_i 是单调递增的，因此我们考虑将边按照 X_i 从小到大排序，并依次加入图中。

设 g_i 代表能使用第 i 条边的最晚出发时间，则在加入这条边的时候我们能利用之前已求出的 g_j 求出 g_i。

具体地，g_i = \max_{B_j=A_i,Y_j \leq X_i}g_j，特别地，当 u_i = 1，则 g_i = A_i。

这部分可以将每一个点的入边按 Y 排序，对每个点动态开点线段树，完成单点修改与区间查 \max 的操作。

具体见实现，注意区间求 \max 的初值要赋为 -1，不然你会像我的模拟赛一样保龄。

气死我了！

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int rt[maxn], id[maxn], pas[maxn], n, m, X, T, pre[maxn], cnt;
struct node {
    int u, v, l, r, id;
}g[maxn];
struct Seg {
    int ls, rs, val;
}tr[maxn * 32];
vector<node> vec[maxn];
void pushup(int p) {
    if(!tr[p].ls && !tr[p].rs) return;
    if(!tr[p].ls) tr[p].val = tr[tr[p].rs].val;
    else if(!tr[p].rs) tr[p].val = tr[tr[p].ls].val;
    else tr[p].val = max(tr[tr[p].ls].val, tr[tr[p].rs].val);
}
int update(int p, int l, int r, int nl, int k) {
    if(!p) p = ++ cnt;
    if(l == r) {
        tr[p].val = k;
        return p;
    }
    int mid = (l + r) >> 1;
    if(nl <= mid) tr[p].ls = update(tr[p].ls, l, mid, nl, k);
    else tr[p].rs = update(tr[p].rs, mid + 1, r, nl, k);
    pushup(p);
    return p;
}
int query(int p, int l, int r, int nl, int nr) {
    if(!p) return -1;
    if(nl <= l && r <= nr) return tr[p].val;
    int mid = (l + r) >> 1, res = -1; 
    if(nl <= mid) res = max(res, query(tr[p].ls, l, mid, nl, nr));
    if(nr > mid) res = max(res, query(tr[p].rs, mid + 1, r, nl, nr));
    return res;
}
void solve() {
    cin >> X;
    int l = 0, r = vec[n].size() - 1, res = -1;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(vec[n][mid].r <= X) res = mid, l = mid + 1;
        else r = mid - 1; 
    }
    if(res == -1) cout << -1 << '\n';
    else cout << pre[res] << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1, u, v, l, r;i <= m;i++) {
        cin >> u >> v >> l >> r;
        g[i] = {u, v, l, r, i};
        vec[v].push_back({u, v, l, r, i});
    }
    for(int i = 1;i <= n;i++) {
        sort(vec[i].begin(), vec[i].end(), [](node a, node b) {return a.r < b.r;});
        for(int j = 0;j < vec[i].size();j++) {
            id[vec[i][j].id] = j;
        }
    }
    sort(g + 1, g + 1 + m, [](node a, node b) {return a.l < b.l;});
    for(int i = 1;i <= m;i++) {
        if(g[i].u == 1) {
            pas[g[i].id] = g[i].l;
        }
        else {
            int l = 0, r = vec[g[i].u].size() - 1, res = -1;
            while(l <= r) {
                int mid = (l + r) >> 1;
                if(vec[g[i].u][mid].r <= g[i].l) res = mid, l = mid + 1;
                else r = mid - 1;
            }
            if(res == -1) pas[g[i].id] = -1;
            else pas[g[i].id] = query(rt[g[i].u], 0, vec[g[i].u].size() - 1, 0, res);
        }
        rt[g[i].v] = update(rt[g[i].v], 0, vec[g[i].v].size() - 1, id[g[i].id], pas[g[i].id]);
    }
    pre[0] = pas[vec[n][0].id];
    for(int i = 1;i < vec[n].size();i++) pre[i] = max(pre[i - 1], pas[vec[n][i].id]);
    cin >> T;
    while(T --) solve();
}