【大联盟】20230701 传送（b） QOJ1878 【No Rest for the Wicked】

题目描述

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;
}