OI - Tourists(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Tourists(Codeforces)

发表于 分类于 Valine：

学了圆方树还是写一个博客

# 题面

> 洛谷 CF487E

> Codeforces 487E

点击展开/折叠题面

Cyberland 有 n 座城市，编号从 1 到 n，有 m 条双向道路连接这些城市。第 j 条路连接城市 $a_j$ 和 $b_j$。

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

每一个游客的游览路径都有固定起始城市和终止城市，且不会经过重复的城市。他们会在路径上的城市中，售价最低的那个城市购买纪念品。

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

你要处理 q 个操作：

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

# 解析

先找到图上所有点双，在点双中任意三点 a,b,c 都存在 $a\to b\to c$ 的简单路径，于是我们每到达一个点双，就一定能够到达该点双中权值最小的点。

点双？路径？——圆方树。

把圆方树建出来，每个方点存储它周围所有圆点的最小权。然后直接查圆方树上两点最小权即可，因为有修改，用树链剖分就可以了。

真的可以了吗？我们看一看修改，假如修改了圆点 u 的权，那么它周围所有的方点权要跟着更新……然而圆点周围的方点个数是 $O(n)$ 的（菊花图）。于是不能这样做，考虑更改方点权值的定义——不是周围所有圆点的最小权，而是我们指定圆方树的根（节点1），然后方点的权值定义为它的所有儿子节点（肯定是圆点，因为方圆交替）的最小权。

这样修改圆点权时，就只需要更新其父节点的权就可以了。

但是这样又有一个 bug，当若询问 $s\to t$，而 $\operatorname{LCA}(s,t)$ 是方点，其父亲节点的权值并没有统计到该方点上，但是这个父节点也在点双内，应该是可以走到的。于是如果发现 $\operatorname{LCA}(s,t)$ 是方点，则额外计算 LCA 的父亲的贡献。

# 源代码

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;
const int N=1e5+10;

struct GRAPH{
	int head[N<<1],nxt[N<<2],to[N<<2],ncnt;
	void AddEdge(int u,int v){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,head[u]=p;
		nxt[q]=head[v],to[q]=u,head[v]=q;
	}
	int operator [](const int &u){return head[u];}
};
GRAPH Gr,Rst;

struct STACK{
	int ary[N],ntop;
	void Push(int x){ary[++ntop]=x;}
	void Pop(){ary[ntop--]=0;}
	int Top(){return ary[ntop];}
}St;

int n,m,ndfn,npnt;
int val[N<<1],low[N];
int dfn[N<<1],tp[N<<1],wei[N<<1],anc[N<<1],dep[N<<1],siz[N<<1],idfn[N<<1];
priority_queue< pii,vector<pii>,greater<pii> > smn[N];

inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
inline char Rc(){
	register int c=getchar();
	while(c!='A' && c!='C') c=getchar();
	return (char)c;
}
void Tarjan(int u){
	dfn[u]=low[u]=++ndfn;
	St.Push(u);
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(dfn[v]){low[u]=min(low[u],dfn[v]);continue;}
		Tarjan(v);
		low[u]=min(low[u],low[v]);
		if(low[v]==dfn[u]){
			npnt++;
			Rst.AddEdge(npnt,u);//printf("+ %d %d\n",npnt,u);
			for(int tmp=-1;tmp!=v;St.Pop())
				Rst.AddEdge(npnt,tmp=St.Top());//printf("+ %d %d\n",npnt,St.Top());
		}
	}
}
void DFS1(int u,int fa){
	siz[u]=1,anc[u]=fa,dep[u]=dep[fa]+1;
	for(int it=Rst[u];it;it=Rst.nxt[it]){
		int v=Rst.to[it];
		if(v==fa) continue;
		if(u>n){
			val[u]=min(val[u],val[v]);
			smn[u-n].push(make_pair(val[v],v));
		}
		DFS1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[wei[u]]) wei[u]=v;
	}
}
void DFS2(int u,int tp_){
	idfn[dfn[u]=++ndfn]=u,tp[u]=tp_;
	if(wei[u]) DFS2(wei[u],tp_);
	else return;
	for(int it=Rst[u];it;it=Rst.nxt[it]){
		int v=Rst.to[it];
		if(v==wei[u] || v==anc[u]) continue;
		DFS2(v,v);
	}
}
struct SEGTREE{
	int mn[N<<2];
	#define idx(l,r) (((l)!=(r))|((l)+(r)))
	void Build(int le,int ri){
		if(le==ri){
			mn[idx(le,ri)]=val[idfn[le]];
			return;
		}
		int mi=(le+ri)>>1;
		Build(le,mi),Build(mi+1,ri);
		PushUp(le,ri);
	}
	void PushUp(int le,int ri){
		int mi=(le+ri)>>1;
		mn[idx(le,ri)]=min(mn[idx(le,mi)],mn[idx(mi+1,ri)]);
	}
	void Modify(int le,int ri,int po,int key){
		if(le==ri){
			mn[idx(le,ri)]=key;
			return;
		}
		int mi=(le+ri)>>1;
		if(po<=mi) Modify(le,mi,po,key);
		else Modify(mi+1,ri,po,key);
		PushUp(le,ri);
	}
	int Query(int le,int ri,int Le,int Ri){
		if(Le<=le && ri<=Ri) return mn[idx(le,ri)];
		int mi=(le+ri)>>1;
		if(Ri<=mi) return Query(le,mi,Le,Ri);
		if(mi<Le) return Query(mi+1,ri,Le,Ri);
		return min(Query(le,mi,Le,Ri),Query(mi+1,ri,Le,Ri));
	}
}Se;
pair<int,int> MQuery(int u,int v){ //<LCA,min>
	int rmn=1e9+10;
	while(tp[u]!=tp[v]){
		if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
		rmn=min(rmn,Se.Query(1,ndfn,dfn[tp[u]],dfn[u]));
		u=anc[tp[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	rmn=min(rmn,Se.Query(1,ndfn,dfn[u],dfn[v]));
	return make_pair(u,rmn);
}
int main(){
	npnt=n=Ri(),m=Ri();
	int cas=Ri();
	memset(val,0x3f,sizeof val);
	for(int i=1;i<=n;i++) val[i]=Ri();
	for(int i=1;i<=m;i++) Gr.AddEdge(Ri(),Ri());
	Tarjan(1);
	memset(dfn,0,sizeof dfn);
	DFS1(1,0);
	ndfn=0,DFS2(1,1);
	Se.Build(1,ndfn);
	while(cas--){
		char cmd=Rc();
		int u=Ri(),v=Ri();
		if(cmd=='A'){
			pair<int,int> res=MQuery(u,v);
			int lca=res.first;
			if(lca>n) res.second=min(res.second,val[anc[lca]]);
			printf("%d\n",res.second);
		}
		else{
			val[u]=v;
			if(anc[u]>n){
				int fa=anc[u]-n;
				while(!smn[fa].empty() && smn[fa].top().first!=val[smn[fa].top().second])
					smn[fa].pop();
				smn[fa].push(make_pair(val[u],u));
				Se.Modify(1,ndfn,dfn[fa+n],smn[fa].top().first);
			}
			Se.Modify(1,ndfn,dfn[u],val[u]);
		}
	}
	return 0;
}

THE END

Thanks for reading!