题目描述
here。
题解
考虑一条路径上只有 \(a\) 的前缀 \(\max\) 才是有用的，不妨考虑按照前缀 \(\max\) 来划分。可以发现，这些连续段直接存在单向边连接。
现在，我们考虑如何求出这些连续段。一个点 \(i\) 可以接在前缀 \(\max\) 为 \(a_j\) 的后面当且仅当 \(a_j\le a_i\le b_j\)，所以，对于 \(j\) 可行的前缀 \(\max\) 的值是一个区间。
于是，我们考虑线段树分治来维护出可行的连通块。并且，我们先递归右子树、再递归左子树，类似拓扑排序一样从大往小更新答案。
时间复杂度 \(O(n\log^2 n)\)。
代码
记录。
#include <bits/stdc++.h>
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 2e5 + 10;
int n, m, a[N], b[N], c[N], fa[N], sz[N], ans[N], t[N << 1], tot;
vector <int> v[N], seg[N << 3], qq[N << 3];
void change(int num, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) {
seg[num].push_back(x);
return;
} int mid = (l + r) >> 1;
if (mid >= L) change(li, L, R, x);
if (mid < R) change(ri, L, R, x);
}
void modify(int num, int l, int r, int x, int y) {
if (l == r) {
qq[num].push_back(y);
return;
} int mid = (l + r) >> 1;
if (mid >= x) modify(li, x, y);
else modify(ri, x, y);
}
bool vis[N];
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
void query(int num, int l, int r) {
vector <pair <int, int>> lst;
for (int i: seg[num]) {
vis[i] = true;
for (int j: v[i]) if (vis[j]) {
int tx = find(i), ty = find(j);
if (tx == ty) continue;
if (sz[tx] < sz[ty]) swap(tx, ty);
lst.emplace_back(tx, ty);
sz[tx] += sz[ty];
chkmax(c[tx], c[ty]);
fa[ty] = tx;
}
}
if (l == r) {
for (int i: qq[num]) {
int id = find(i);
ans[i] = c[id];
for (int j: v[i]) chkmax(c[find(j)], c[id]);
}
} else {
int mid = (l + r) >> 1;
query(ri);
query(li);
}
while (lst.size()) {
fa[lst.back().second] = lst.back().second;
sz[lst.back().first] -= sz[lst.back().second];
chkmax(c[lst.back().second], c[lst.back().first]);
lst.pop_back();
}
for (int i: seg[num]) vis[i] = false;
}
signed main() {
//freopen("b.in", "r", stdin);
//freopen("b.out", "w", stdout);
read(n), read(m);
F(i, 1, n) read(a[i]), read(b[i]), read(c[i]), t[++tot] = a[i], t[++tot] = b[i], fa[i] = i, sz[i] = 1;
sort(t + 1, t + tot + 1);
tot = unique(t + 1, t + tot + 1) - t - 1;
F(i, 1, n) a[i] = lower_bound(t + 1, t + tot + 1, a[i]) - t, b[i] = lower_bound(t + 1, t + tot + 1, b[i]) - t, change(1, 1, tot, a[i], b[i], i), modify(1, 1, tot, a[i], i);
F(i, 1, m) {
int x, y; read(x), read(y);
v[x].push_back(y);
v[y].push_back(x);
} query(1, 1, tot);
F(i, 1, n) cout << ans[i] << ' ';
return 0;
}