乌鲁鲁高速公路

题解

简单题，感觉没 D2T2 难。

有一个很自然的想法：建议一个偏序关系 $u \rightarrow v$ 表示 $u$ 的深度比 $v$ 的深度大，然后 topu 排序求解。

然后优化建图方法更是典中典。

然后就做完了，时间复杂度 $O(\sum k \log n)$。

代码

挺好写的

#include <bits/stdc++.h>
#define Code using
#define by namespace
#define zzx std
Code by zzx;

const int N = 100000, B = 20;

struct node {
    int x, y, id;
}a[N + 10];

int n, k;
int l[N + 10], r[N + 10];
int pos[N + 10], rnk[N + 10];
pair<int, int> lsh[N + 10];

vector<int> e[6 * N + 10], s[N + 10];
int ind[6 * N + 10], vis[6 * N + 10];
queue<int> q;

void add(int u, int v) {
    e[u].push_back(v); ++ind[v];
}

void build(int s, int t, int p) {
    vis[p + n + k] = 1;
    if(s == t) {
        add(lsh[s].second + n, p + n + k); return;
    }
    int mid = (s + t) >> 1;
    build(s, mid, p * 2); build(mid + 1, t, p * 2 + 1);
    add(p * 2 + n + k, p + n + k);
    add(p * 2 + 1 + n + k, p + n + k);
}

void update(int s, int t, int p, int x, int y, int id) {
    if(x <= s && t <= y) {
       add(p + n + k, id);
       return;
    }
    int mid = (s + t) >> 1;
    if(x <= mid) update(s, mid, p * 2, x, y, id);
    if(mid < y) update(mid + 1, t, p * 2 + 1, x, y, id);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> l[i] >> r[i];
    cin >> k;
    for(int i = 1; i <= k; ++i) {
        cin >> pos[i]; lsh[i] = make_pair(pos[i], i);
        int m, la = 0; cin >> m;
        for(int j = 1; j <= m; ++j) {
            int u; cin >> u;
            add(u, i + n); s[u].push_back(i);
            if(la) add(la, u);
            la = u;
        }
    }
    sort(lsh + 1, lsh + k + 1);
    for(int i = 1; i <= k; ++i) rnk[lsh[i].second] = i;
    build(1, k, 1);
    for(int i = 1; i <= n + k; ++i) vis[i] = 1;
    for(int i = 1; i <= n; ++i) {
        int x = lower_bound(lsh + 1, lsh + k + 1, make_pair(l[i], 0)) - lsh;
        int y = upper_bound(lsh + 1, lsh + k + 1, make_pair(r[i], k + 1)) - lsh - 1;
        if(x > y) continue;
        for(int &j : s[i]) j = rnk[j];
        sort(s[i].begin(), s[i].end());
        for(int j = 0; j < (int)s[i].size(); ++j) {
            if(s[i][j] == x) {
                ++x; continue;
            }
            update(1, k, 1, x, s[i][j] - 1, i);
            x = s[i][j] + 1;
        }
        if(x <= y) update(1, k, 1, x, y, i);
    }
    for(int i = 1; i <= n + 5 * k; ++i) {
        if(!vis[i]) continue;
        if(!ind[i]) q.push(i);
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if(u <= n) cout << u << ' ';
        for(int v : e[u]) {
            --ind[v];
            if(!ind[v]) q.push(v);
        }
    }
    return 0;
}