考虑把边按到达时间排序，然后从前往后扫并做一个 dp。
设 \(f_u\) 表示 \(1\) 到达 \(u\) 的最晚出发时间。那么对于一条边 \((u, v, a, b)\)：
- 若 \(u = 1\)，则 \(f_v = \max(f_v, x)\)；
- 否则 \(f_v = \max(f_v, f'_u)\)，\(f'_u\) 为只考虑到达时间 \(\le x\) 的边时 \(f_u\) 的值。
可持久化数组用主席树维护，复杂度 \(O((n + m + q) \log (n + m + q))\)。
询问可以离线或在线回答。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
char c = getchar();
int x = 0;
bool f = 0;
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return f ? -x : x;
}
const int maxn = 300100;
int n, m, q, ans[maxn];
pii qq[maxn];
struct node {
int u, v, a, b;
} E[maxn];
int rt[maxn], ls[maxn * 30], rs[maxn * 30], val[maxn * 30], ntot;
int build(int l, int r) {
int rt = ++ntot;
if (l == r) {
val[rt] = -1;
return rt;
}
int mid = (l + r) >> 1;
ls[rt] = build(l, mid);
rs[rt] = build(mid + 1, r);
return rt;
}
int update(int rt, int l, int r, int x, int y) {
int dir = ++ntot;
ls[dir] = ls[rt];
rs[dir] = rs[rt];
val[dir] = val[rt];
if (l == r) {
val[dir] = max(val[dir], y);
return dir;
}
int mid = (l + r) >> 1;
if (x <= mid) {
ls[dir] = update(ls[dir], l, mid, x, y);
} else {
rs[dir] = update(rs[dir], mid + 1, r, x, y);
}
return dir;
}
int query(int rt, int l, int r, int x) {
if (l == r) {
return val[rt];
}
int mid = (l + r) >> 1;
return x <= mid ? query(ls[rt], l, mid, x) : query(rs[rt], mid + 1, r, x);
}
void solve() {
n = read();
m = read();
for (int i = 1; i <= m; ++i) {
E[i].u = read();
E[i].v = read();
E[i].a = read();
E[i].b = read();
}
q = read();
for (int i = 1; i <= q; ++i) {
qq[i].fst = read();
qq[i].scd = i;
}
sort(qq + 1, qq + q + 1);
sort(E + 1, E + m + 1, [&](const node &a, const node &b) {
return a.b < b.b;
});
int j = 1;
rt[0] = build(1, n);
for (int i = 1; i <= m; ++i) {
rt[i] = rt[i - 1];
int u = E[i].u, v = E[i].v, x = E[i].a, y = E[i].b;
while (j <= q && qq[j].fst < y) {
ans[qq[j].scd] = query(rt[i], 1, n, n);
++j;
}
if (u == 1) {
rt[i] = update(rt[i], 1, n, v, x);
} else {
int l = 1, r = i - 1, pos = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (E[mid].b <= x) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (pos == -1) {
continue;
}
int t = query(rt[pos], 1, n, u);
if (t <= x) {
rt[i] = update(rt[i], 1, n, v, t);
}
}
}
while (j <= q) {
ans[qq[j].scd] = query(rt[m], 1, n, n);
++j;
}
for (int i = 1; i <= q; ++i) {
printf("%d\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}