T1 倒水

不会

T2 让他们联通

原题

时间为边权，然后最小生成树，树剖算出 i 到 i + 1 路径上的边权最大值，然后线段树求 [l, r - 1] 区间的路径最大值就可以了。

还有：

_ _ NKOJ, _ _ _ !

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
#ifdef ONLINE_JUDGE
char buf[1 << 23] , * p1 = buf , * p2 = buf , obuf[1 << 23] , * O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
#define endl '\n'
inline int read() {
	int x = 0 , f = 1;char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1;ch = getchar(); }
	while (isdigit(ch)) x = x * 10 + (ch ^ 48) , ch = getchar();
	return x * f;
}
//#define max(x, y) ((x) > (y) ? (x) : (y))
int n, m, q;
int f[N];
vector<pair<int, int> > g[N];
int val[N];
int find (int x) {
	if(f[x] == x) return f[x];
	return f[x] = find(f[x]);
}
int dfn[N], to[N], siz[N], top[N], dep[N], son[N], fa[N], tmp;
int link_cnt[N];
struct tree {
	int ma[N * 4], val[N];
	#define mid (l + r >> 1)
	#define ls p << 1, l, mid
	#define rs (p << 1) | 1, mid + 1, r
	void build(int p, int l, int r) {
		if(l == r) ma[p] = val[l];
		else build(ls), build(rs), ma[p] = max(ma[p << 1], ma[p << 1 | 1]);;
	}
	int getmax (int p, int l, int r, int ql, int qr) {
		if(ql <= l && r <= qr) return ma[p];
		if(ql > r || qr < l) return -inf;
		return max(getmax(ls, ql, qr), getmax(rs, ql, qr));
	}
}t, t2;
void dfs1 (int u, int fath) {
	dep[u] = dep[fath] + 1, siz[u] = 1, fa[u] = fath;
	for (auto e : g[u]) {
		int v = e.first, w = e.second;
		if(v == fath) continue;
		val[v] = w;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]]) son[u] = v;
	}
}
void dfs2 (int u, int tp) {
	top[u] = tp, dfn[u] = ++ tmp, to[tmp] = u;
	if(son[u]) dfs2(son[u], tp);
	for (auto e : g[u]) {
		int v = e.first;
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
inline int getmax (int u, int v) {
	int res = -inf;
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		int tmp = t.getmax(1, 1, n, dfn[top[u]], dfn[u]);
		res = max(res, tmp);
		u = fa[top[u]];
	}
	if(dep[u] < dep[v]) swap(u, v);
	int tmp = t.getmax(1, 1, n, dfn[v] + 1, dfn[u]);
	res = max(res, tmp);
	return res;
}
int maxn[N][30], log_2[N];
inline void init (int len, int value[] ) {
	for (int i = 1; i <= len; i ++) maxn[i][0] = value[i];
	for (int i = 2; i <= len; i ++) log_2[i] = log_2[i >> 1] + 1;
	for (int j = 1; (1 << j) <= len; j ++) {
		for (int i = 1; i + (1 << j) - 1 <= len; i ++) {
			maxn[i][j] = max(maxn[i][j - 1], maxn[i + (1 << j - 1)][j - 1]);
		}
	}
}
inline int get_max (int l, int r) {
	int len = log_2[r - l + 1];
	return max(maxn[l][len], maxn[r - (1 << len) + 1][len]);
}

void solve () {
	tmp = 0;
	n = read(), m = read(), q = read();
	for (int i = 1; i <= n; i ++) f[i] = i, g[i].clear(), son[i] = 0;
	for (int i = 1; i <= m; i ++) {
		int u, v;
		u = read(), v = read();
		if(find(u) != find(v)) {
			f[find(v)] = find(u);
			g[u].push_back({v, i});
			g[v].push_back({u, i});
		}
	}
	dfs1 (1, -1), dfs2 (1, 1);
	for (int i = 1; i <= n; i ++) t.val[i] = val[to[i]];
	t.build(1, 1, n);
	for (int i = 1; i < n; i ++) {
		link_cnt[i] = getmax(i, i + 1);
	}
	init(n - 1, link_cnt);
	while(q --) {
		int l, r;
		l = read(), r = read();
		if(l == r) cout << 0 << ' ';
		else cout << get_max(l, r - 1) << ' ';
	}
	cout << endl;
}


signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

T3 通信网络

不会

T4 3sum

原题

不会