2019.04.02【CodeForces487】E. Tourists（圆方树）（树链剖分）（线段树）

传送门

---

解析：

我们发现题目中简单路径这个条件其实就是将点双缩点后，重构树上路径经过的所有点双里面的点。

于是构建广义圆方树。这道题还是为了方便处理，将所有割边改造为方点。

按照套路，所有方点维护亲儿子的信息，直接开一个multiset就行了。

显然我们需要询问路径上最小值，上树剖和线段树维护，然后在询问的时候特判路径LCA为方点的情况。

代码有点长，但是没什么细节，很好写。

---

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<20|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	inline int getint(){
		re char c;
		while(!isdigit(c=gc()));re int num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline char getalpha(){
		re char c;
		while(!isalpha(c=gc()));return c;
	}
}
using namespace IO;

using std::cout;
using std::cerr;

cs int N=1e5+5;

int n,m,q;
int w[N<<1];
int ext;
namespace Tree{
	static cs int N=::N<<1;
	
	int last[N],nxt[N<<1],to[N<<1],ecnt;
	inline void addedge(int u,int v){
		nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v;
		nxt[++ecnt]=last[v],last[v]=ecnt,to[ecnt]=u;
	}
	
	int fa[N],dep[N],top[N],siz[N],son[N];
	int in[N],pos[N],dfs_clock;
	
	void dfs1(int u){
		siz[u]=1;
		for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]])if(v!=fa[u]){
			fa[v]=u;
			dep[v]=dep[u]+1;
			dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
	}
	
	void dfs2(int u){
		pos[in[u]=++dfs_clock]=u;
		if(son[u]){
			top[son[u]]=top[u];
			dfs2(son[u]);
		}
		else return ;
		for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]])if(v!=fa[u]&&v!=son[u]){
			top[v]=v;
			dfs2(v);
		}
	}
	
	int mn[N<<2];
	inline void build(int k,int l,int r){
		if(l==r){
			mn[k]=w[pos[l]];
			return ;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		mn[k]=std::min(mn[k<<1],mn[k<<1|1]);
	}
	
	inline void update(int k,int l,int r,cs int &p){
		if(l==r){
			mn[k]=w[pos[l]];
			return ;
		}
		int mid=(l+r)>>1;
		if(p<=mid)update(k<<1,l,mid,p);
		if(mid<p)update(k<<1|1,mid+1,r,p);
		mn[k]=std::min(mn[k<<1],mn[k<<1|1]);
	}
	
	inline int query(int k,int l,int r,cs int &ql,cs int &qr){
		if(ql<=l&&r<=qr)return mn[k];
		int mid=(l+r)>>1;
		if(qr<=mid)return query(k<<1,l,mid,ql,qr);
		if(mid<ql)return query(k<<1|1,mid+1,r,ql,qr);
		return std::min(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr));
	}
	
	std::multiset<int> s[N>>1];
	
	inline void build(){
		dfs1(1);top[1]=1;dfs2(1);
		for(int re i=2;i<=n;++i)s[fa[i]-n].insert(w[i]);
		for(int re i=n+1;i<=ext;++i)w[i]=s[i-n].empty()?0x3f3f3f3f:*s[i-n].begin();
		build(1,1,ext);
	}
	
	inline void modify(int u,int val){
		if(u==1){
			w[u]=val;
			update(1,1,ext,in[u]);
			return ;
		}
		int f=fa[u]-n;
		s[f].erase(s[f].lower_bound(w[u]));
		w[u]=val;update(1,1,ext,in[u]);
		s[f].insert(w[u]);
		if(w[f+n]==*s[f].begin())return ;
		w[f+n]=*s[f].begin();
		update(1,1,ext,in[f+n]);
	}
	
	inline int query_path(int u,int v){
		int res=0x3f3f3f3f;
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])std::swap(u,v);
			res=std::min(res,query(1,1,ext,in[top[u]],in[u]));
			u=fa[top[u]];
		}
		if(dep[u]>dep[v])std::swap(u,v);
		res=std::min(res,query(1,1,ext,in[u],in[v]));
		if(u>n)res=std::min(res,w[fa[u]]);
		return res;
	}
}

namespace Graph{
	static cs int N=::N;
	static cs int M=::N;
	int last[N],nxt[M<<1],to[M<<1],ecnt;
	inline void addedge(int u,int v){
		nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v;
		nxt[++ecnt]=last[v],last[v]=ecnt,to[ecnt]=u;
	}
	
	int dfn[N],low[N],dfs_clock;
	int sta[N],top;
	inline void tarjan(int u){
		dfn[u]=low[u]=++dfs_clock;
		sta[++top]=u;
		for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]]){
			if(!dfn[v]){
				tarjan(v);
				low[u]=std::min(low[u],low[v]);
				if(low[v]>=dfn[u]){
					Tree::addedge(++ext,u);
					int x;
					do{
						x=sta[top--];
						Tree::addedge(ext,x);
					}while(x!=v);
				}
			}
			else low[u]=std::min(low[u],dfn[v]);
		}
	}
}

signed main(){
	ext=n=getint(),m=getint(),q=getint();
	for(int re i=1;i<=n;++i)w[i]=getint();
	for(int re i=1;i<=m;++i)Graph::addedge(getint(),getint());
	Graph::tarjan(1);
	Tree::build();
	while(q--)switch(getalpha()){
		case 'C':{
			int u=getint(),v=getint();
			Tree::modify(u,v);
			break;
		}
		case 'A':{
			cout<<Tree::query_path(getint(),getint())<<"\n";
			break;
		}
	}
	return 0;
}