UOJ #30. [CF Round #278] Tourists

题目大意 :

有一张 \(n\) 个点， \(m\) 条边的无向图，每一个点有一个点权 \(a_i\) ，你需要支持两种操作，第一种操作修改一个点的点权，第二种操作给出 \(u, v\)，求一个点 \(x\) ，存在一条 \(u-x-v\) 不经过重复点的路径且 \(a_x\) 最小

\(1 \leq n,m \leq 10^5\)

解题思路 :

考虑如果 \(u-x\) 和 \(x-v\) 经过了同一个割点，那么一定不合法，也就是说 \(x\) 一定在 \(u-v\) 之间的点双联通分量里。于是将圆方树建出来，对于每一个方点用一个 \(\text{multiset}\) 维护最小值，树链剖分维护路径答案，注意特判 \(lca\) 是方点的情况

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

	int f = 0, ch = 0; x = 0;

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

#define lson (u << 1)

#define rson (u << 1 | 1)

const int N = 1000005;

char str[20];

vector<int> g[N];

int ass[N], n, m, q;

struct SegmentTree{

	int s[N<<2];

	inline SegmentTree(){ memset(s, 127, sizeof(s)); }

	inline void modify(int u, int l, int r, int pos, int x){

		if(l == r) return (void) (s[u] = x);

		int mid = l + r >> 1;

		if(pos <= mid) modify(lson, l, mid, pos, x);

		else modify(rson, mid + 1, r, pos, x);

		s[u] = min(s[lson], s[rson]);

	}

	inline int query(int u, int l, int r, int L, int R){

		if(l >= L && r <= R) return s[u];

		int mid = l + r >> 1, res = inf;

		if(L <= mid) res = min(query(lson, l, mid, L, R), res);

		if(mid < R) res = min(query(rson, mid + 1, r, L, R), res);

		return res;

	}

}Seg;

namespace Gao{

	multiset<int> st[N];

	vector<int> g[N];

	int dep[N], sz[N], ff[N], ms[N], dfn[N], top[N], cnt;

	inline void dfs(int u, int fa){

		dep[u] = dep[fa] + 1, sz[u] = 1, ff[u] = fa;

		if(fa > n) st[fa].insert(ass[u]);

		for(int i = 0; i < g[u].size(); i++){

			int v = g[u][i];

			if(v == fa) continue;

			dfs(v, u), sz[u] += sz[v];

			if(sz[v] > sz[ms[u]]) ms[u] = v;

		}

	}

	inline void split(int u, int chain, int fa){

		dfn[u] = ++cnt, top[u] = chain;

		int tmp = u <= n ? ass[u] : (*st[u].begin());

		Seg.modify(1, 1, 2 * n, dfn[u], tmp);

		if(ms[u]) split(ms[u], chain, u);

		for(int i = 0; i < g[u].size(); i++){

			int v = g[u][i];

			if(v == fa || v == ms[u]) continue;

			split(v, v, u);

		}

	}

	inline int query(int x, int y){

		int res = inf;

		while(top[x] != top[y]){

			if(dep[top[x]] < dep[top[y]]) swap(x, y);

			res = min(res, Seg.query(1, 1, 2 * n, dfn[top[x]], dfn[x]));

			x = ff[top[x]];

		}

		if(dfn[x] > dfn[y]) swap(x, y);

		res = min(res, Seg.query(1, 1, 2 * n, dfn[x], dfn[y]));

		if(ff[x] <= n && ff[x]) res = Min(res, ass[ff[x]]);

		return res;

	}

	inline void modify(int x, int y){

		Seg.modify(1, 1, 2 * n, dfn[x], y);

		if(x > 1){

			st[ff[x]].erase(st[ff[x]].find(ass[x]));

			st[ff[x]].insert(y);

			Seg.modify(1, 1, 2 * n, dfn[ff[x]], *(st[ff[x]].begin()));

		}

		ass[x] = y;

	}

}

namespace Graph{

	int a[N], nxt[N], head[N], dfn[N], low[N], st[N], top, Index, id, cnt = 1;

	inline void add(int x, int y){

		a[++cnt] = y, nxt[cnt] = head[x], head[x] = cnt;

	}

	inline void tarjan(int u, int fa){

		dfn[u] = low[u] = ++Index;

		for(int p = head[u]; p; p = nxt[p]){

			if((p ^ 1) == fa) continue;

			int v = a[p];

			if(dfn[v]){ low[u] = min(low[u], dfn[v]); continue; }

			st[++top] = v, tarjan(v, p);

			low[u] = min(low[u], low[v]);

			if(low[v] >= dfn[u]){

				id++;

				for(; st[top] != v; top--){

					Gao::g[id].push_back(st[top]);

					Gao::g[st[top]].push_back(id);

				}

				top--;

				Gao::g[id].push_back(v), Gao::g[v].push_back(id);

				Gao::g[id].push_back(u), Gao::g[u].push_back(id);

			}

		}

	}

	inline void Build(){

		id = n;

		for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, 0);

	}

}

signed main(){

	read(n), read(m), read(q);

	for(int i = 1; i <= n; i++) read(ass[i]);

	for(int i = 1, x, y; i <= m; i++){

		read(x), read(y);

		Graph::add(x, y), Graph::add(y, x);

	}

	Graph::Build();

	Gao::dfs(1, 0), Gao::split(1, 1, 0);

	for(int i = 1, x, y; i <= q; i++){

		scanf("%s", str); read(x), read(y);

		if(str[0] == 'C') Gao::modify(x, y);

		if(str[0] == 'A') printf("%d\n",  Gao::query(x, y));

	}

	return 0;

}

巴特西

UOJ #30. [CF Round #278] Tourists

UOJ #30. [CF Round #278] Tourists

解题思路 :

最新文章

热门文章