[Luogu cf487e] tours (square tree) (tree chain dissection) (line segment tree)

Tourists

Topic link ：luogu CF487E

The main idea of the topic

Here's an undirected graph , Then a little bit of power .
Then you may modify the point weight at a single point every time , Or ask the point with the least weight in all paths between two points .

Ideas

It's not difficult to think of a round square tree when you see all these paths .

Then we consider that the square point is the minimum value of the origin to which it is connected .
Then you will find that if there is any modification, you will get stuck every time $O(n)$（ Meganium ）

Then consider a wonderful way , Is to consider the special place of this figure , It's a tree .
The reason why you get stuck is that you have to update everything , That update must be updated , The question is whether we can update only a part first , Then when you ask, get the missing part .
If the structure of the tree, can we only get our son , Then every time I update, I only update my father .

Then you think about the part of tree chain dissection , That's except LCA Is it OK for Fang Dian to get his father to do anything else .

Then the rest is simple , Just ordinary round square tree , Ordinary tree chain segmentation plus segment tree maintenance minimum .

Code

#include<set>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 100;
int n, m, q, w[N << 1], tot;
vector <int> G[N], GG[N << 1];
multiset <int> sum[N];

struct SLPF {
    
	int dfn[N << 1], son[N << 1], sz[N << 1], fa[N << 1], top[N << 1], a[N << 3], deg[N << 1], dy[N << 1];
	
	void dfs1(int now, int father) {
    
		sz[now] = 1; fa[now] = father; deg[now] = deg[father] + 1;
		for (int i = 0; i < GG[now].size(); i++) {
    int x = GG[now][i]; if (x == father) continue;
			dfs1(x, now); sz[now] += sz[x]; if (sz[x] > sz[son[now]]) son[now] = x;
		}
		if (now > n) {
    
			for (int i = 0; i < GG[now].size(); i++) {
    int x = GG[now][i]; if (x == father) continue;
				sum[now - n].insert(w[x]);
			}
			w[now] = *sum[now - n].begin();
		}
	}
	
	void dfs2(int now, int father) {
    
		dfn[now] = ++dfn[0]; dy[dfn[0]] = now;
		if (son[now]) {
    
			top[son[now]] = top[now]; dfs2(son[now], now);
		}
		for (int i = 0; i < GG[now].size(); i++) {
    int x = GG[now][i]; if (x == father || x == son[now]) continue;
			top[x] = x; dfs2(x, now);
		}
	}
	
	void up(int now) {
    
		a[now] = min(a[now << 1], a[now << 1 | 1]);
	}
	
	void build(int now, int l, int r) {
    
		if (l == r) {
    
			a[now] = w[dy[l]]; return ;
		}
		int mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now);
	}
	
	void change(int now, int l, int r, int pl) {
    
		if (l == r) {
    
			a[now] = w[dy[pl]]; return ;
		}
		int mid = (l + r) >> 1;
		if (pl <= mid) change(now << 1, l, mid, pl); else change(now << 1 | 1, mid + 1, r, pl);
		up(now);
	}
	
	int query(int now, int l, int r, int L, int R) {
    
		if (L <= l && r <= R) {
    
			return a[now];
		}
		int mid = (l + r) >> 1, re = 2e9;
		if (L <= mid) re = min(re, query(now << 1, l, mid, L, R));
		if (mid < R) re = min(re, query(now << 1 | 1, mid + 1, r, L, R));
		return re;
	}
	
	int ask(int x, int y) {
    
		int re = 2e9;
		while (top[x] != top[y]) {
    
			if (deg[top[x]] < deg[top[y]]) swap(x, y);
			re = min(re, query(1, 1, tot, dfn[top[x]], dfn[x]));
			x = fa[top[x]];
		}
		if (deg[x] > deg[y]) swap(x, y);
		re = min(re, query(1, 1, tot, dfn[x], dfn[y]));
		if (x > n) re = min(re, w[fa[x]]);
		return re;
	}
}T;

struct YF_tree {
    
	int dfn[N], low[N], sta[N];
	
	void link(int x, int y) {
    GG[x].push_back(y); GG[y].push_back(x);}
	
	void tarjan(int now) {
    
		dfn[now] = low[now] = ++dfn[0]; sta[++sta[0]] = now;
		for (int i = 0; i < G[now].size(); i++) {
    int x = G[now][i];
			if (!dfn[x]) {
    
				tarjan(x); low[now] = min(low[now], low[x]);
				if (dfn[now] == low[x]) {
    
					tot++;
					while (sta[sta[0]] != x) {
    
						link(sta[sta[0]], tot); sta[0]--;
					}
					link(sta[sta[0]], tot); sta[0]--;
					link(now, tot);
				}
			}
			else low[now] = min(low[now], dfn[x]);
		}
	}
	
	void Init() {
    
		tot = n;
		for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
		T.dfs1(1, 0); T.dfs2(1, 0);
	}
}H;

int main() {
    
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	for (int i = 1; i <= m; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		G[x].push_back(y); G[y].push_back(x); 
	}
	
	H.Init();
	T.build(1, 1, tot);
	
	while (q--) {
    
		char c = getchar(); while (c != 'C' && c != 'A') c = getchar();
		if (c == 'A') {
    
			int x, y; scanf("%d %d", &x, &y);
			printf("%d\n", T.ask(x, y));
		}
		else {
    
			int x, y; scanf("%d %d", &x, &y);
			if (T.fa[x]) {
    
				sum[T.fa[x] - n].erase(w[x]); sum[T.fa[x] - n].insert(y);
				w[T.fa[x]] = *sum[T.fa[x] - n].begin(); T.change(1, 1, tot, T.dfn[T.fa[x]]);
			}
			w[x] = y; T.change(1, 1, tot, T.dfn[x]);
		}
	}
	
	return 0;
}