Codeforces487E题解

发表于

较有难度的圆方树+树剖题目

Description

Cyberland 有 n 座城市，编号从 1 到 n，有 m 条双向道路连接这些城市。第 j 条路连接城市 aj 和 bj。每天，都有成千上万的游客来到 Cyberland 游玩。

在每一个城市，都有纪念品售卖，第 i 个城市售价为 wi。这个售价有时会变动。

每一个游客的游览路径都有固定起始城市和终止城市，且不会经过重复的城市。

他们会在路径上的城市中，售价最低的那个城市购买纪念品。

你能求出每一个游客在所有合法的路径中能购买的最低售价是多少吗？

你要处理 q 个操作：

C a w： 表示 a 城市的纪念品售价变成 w。 A a b： 表示有一个游客要从 a 城市到 b 城市，你要回答在所有他的旅行路径中最低售价的最低可能值。

输入格式

第一行包含用一个空格隔开的三个数，n、m、q。

接下来 n 行，每行包含一个数 wi。

接下来 m 行，每行包含用一个空格隔开的两个数 aj, bj。（1≤aj,bj≤n,aj≠bj1≤aj,bj≤n,aj≠bj）

数据保证没有两条道路连接同样一对城市，也没有一条道路两端是相同的城市。并且任意两个城市都可以相互到达。

接下来 q 行，每行是C a w 或 A a b ，描述了一个操作。 输出格式

对于每一个A类操作，输出一行表示对应的答案。

Samples

Input #1

1
2
3
4
5
6
7
8
9
10
3 3 3
1
2
3
1 2
2 3
1 3
A 2 3
C 1 5
A 2 3

Output #1

1
2
1
2

Input #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
7 9 4
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 2 3
A 6 4
A 6 7
A 3 3

Output #2

1
2
3
4
2
1
5
3

Solution

看到询问有关维护图上两点之间简单路径信息的操作, 很容易可以想到圆方树.

我们首先建出圆方树, 令方点维护与之相连的圆点的权值最小值, 那么问题可以转化为路径上求最小值.

如果没有修改操作, 那么我们直接对圆方树进行树链剖分, 然后用线段树维护即可.

如果暴力修改点权, 那么需要修改与他相连的所有方点, 显然可以被卡到$\mathcal O(n)$

这时我们就要利用圆方树的性质: 圆方树是棵树(废话), 令方点权值为其儿子圆点的权值最小值, 那么我们直接修改方点即可,

而维护方点的权值, 就直接对于每一个方点维护一个multiset即可. 注意: 在查询的时候若两个点的LCA是方点, 那么需要查一下其父亲圆点的值.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<array>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define RevEdge(x) x^1
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 2e5 + 10;
const int inf = INT_MAX;
int n, m, cnt, dfn[MAXN], low[MAXN], indexs, dfnx[MAXN], tot, SMT[MAXN * 3];
int fa[MAXN], son[MAXN], size[MAXN], depth[MAXN], top[MAXN], rk[MAXN], w[MAXN], q;
long long ans;
std::stack<int> sk;
std::vector<int> G[MAXN << 1], _G[MAXN << 1];
std::multiset<int> X[MAXN];
/* functions */
inline void Tarjan(int u) {
	dfn[u] = low[u] = ++indexs; sk.push(u);
	for(auto v : G[u]) {
		if(!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if(low[v] == dfn[u]) {
				cnt = cnt + 1;
				for(int x = 0; x != v; sk.pop()) {
					x = sk.top();
					_G[cnt].push_back(x);
					_G[x].push_back(cnt);
				}
				_G[cnt].push_back(u);
				_G[u].push_back(cnt);
			}
		}
		else low[u] = std::min(low[u], dfn[v]);
	}
}
inline void DFS1(int u, int f, int dep) {
	depth[u] = dep; fa[u] = f; size[u] = 1;
	for(auto v : _G[u]) {
		if(v == f) continue;
		DFS1(v, u, dep + 1); size[u] += size[v];
		if(size[v] > size[son[u]]) son[u] = v;
	}
}
inline void DFS2(int u, int f, int topf) {
	dfn[u] = ++indexs; top[u] = topf;
	rk[indexs] = u;
	if(son[u]) DFS2(son[u], u, topf);
 	for(auto v : _G[u]) {
		if(v != f && v != son[u]) DFS2(v, u, v);
	}
}
inline void pushUp(int k) {	
	SMT[k] = std::min(SMT[LeftChild(k)], SMT[RightChild(k)]);
}
inline void Build(int l, int r, int k) {
	if(l == r) {SMT[k] = w[rk[l]]; return ;}
	int mid = (l + r) >> 1;
	Build(l, mid, LeftChild(k));
	Build(mid + 1, r,RightChild(k));
	pushUp(k);	
}
inline void Modify(int l, int r, int x, int y, int k) {
	if(l == r) {SMT[k] = y; return ;}
	int mid = (l + r) >> 1;
	if(x <= mid) Modify(l, mid, x, y, LeftChild(k));
	else Modify(mid + 1, r, x, y, RightChild(k));
	pushUp(k);
}
inline int Query(int l, int r, int x, int y, int k) {
	if(r < x || y < l) return inf;
	if(x <= l && r <= y) return SMT[k];
	int mid = (l + r) >> 1;
	return std::min(Query(l, mid, x, y, LeftChild(k)), Query(mid + 1, r, x, y, RightChild(k)));
} 
int main(int argc,char *argv[]){	
	scanf("%d %d %d", &n, &m, &q); 
	FOR(i, 1, n, 1) scanf("%d", &w[i]);
	cnt = n;
	FOR(i, 1, m, 1) {
		int u, v; scanf("%d %d", &u, &v);
		G[u].push_back(v); G[v].push_back(u);
	}
	Tarjan(1); DFS1(1, 0, 1); 
	indexs = 0; DFS2(1, 0, 1);
	FOR(i, 1, n, 1) if(fa[i]) X[fa[i]].insert(w[i]);
	FOR(i, n + 1, cnt, 1) w[i] = *X[i].begin();
	Build(1, cnt, 1);
	while(q --> 0) {
		char op[5]; int x, y;
		scanf("%s %d %d", op, &x, &y);
		if(op[0] == 'C') {
			Modify(1, cnt, dfn[x], y, 1);
			if(fa[x]) {
				int u = fa[x];
				X[u].erase(X[u].lower_bound(w[x]));
				X[u].insert(y);
				if(w[u] != *X[u].begin()) {
					w[u] = *X[u].begin();
					Modify(1, cnt, dfn[u], w[u], 1);
				}
			}
			w[x] = y;
		}
		else {
			int ans = inf;
			while(top[x] != top[y]) {
				if(depth[top[x]] < depth[top[y]]) std::swap(x, y);
				ans = std::min(ans, Query(1, cnt, dfn[top[x]], dfn[x], 1));
				x = fa[top[x]];
			}
			if(dfn[x] > dfn[y]) std::swap(x, y);
			ans = std::min(ans, Query(1, cnt, dfn[x], dfn[y], 1));
			if(x > n) ans = std::min(ans, w[fa[x]]);
			printf("%d\n", ans);
		}
	}
 	return 0; 	
}

THE END