CF487E Tourists（圆方树+树链剖分）

洛谷题目传送门

解题思路

不会圆方树的可以看我的博客圆方树学习记录及例题

首先Tarjan寻找点双连通分量，然后建立圆方树，每个方点存这个点双内的最小点权
将圆方树树链剖分之后，对于修改操作，将这个点连的所有方点的值更新
对于查询操作，直接查询树上两点之间路径的最小值
然后就AC了
怎么可能呢，如果一个圆点连着非常多个方点，那么时间复杂度就飞天了
正确的做法是：
建出圆方树后，每个方节点的值是它的所有子节点的最小值，而不包括父节点
可以用 m u l t i s e t multiset multiset维护每个方点的权值
那么修改操作时，只需要更新这个点和它的父节点就可以了
查询时，如果这两个点的 L C A LCA LCA是方点，他应该有他父亲圆点的值，但是并没有存储，因此在查询一下 L C A LCA LCA的父节点的值就行了
其余的就是树剖的基本操作

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 2e5+7;
const LL INF = 1e9+7; 
const LL maxn=1e5+7;
struct node
{
	LL y,next;
}e[2*N];
LL link[N],t=0,w[N],n,m,q,a[N];
void add(LL x,LL y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
inline LL read()
{
	LL X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
stack<LL> st;
LL dfn[maxn],low[maxn];
bool cut[maxn];
vector<LL> Dcc[N];
LL num=0,root,cnt=0;
LL Size=0;
void tarjan(LL x)
{
	dfn[x]=low[x]=++num;
	st.push(x);
	if(x==root&&link[x]==0)
	{
		Dcc[++cnt].push_back(x);
		return;
	}
	LL flag=0;
	for(LL i=link[x];i;i=e[i].next)
	{
		LL y=e[i].y;
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x])
			{
				flag++;
				if(x!=root||flag>1) cut[x]=1;
				cnt++;
				LL z;
				do
				{
					z=st.top();
					st.pop();
					Dcc[cnt].push_back(z);
				}while(z!=y);
				Dcc[cnt].push_back(x);
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
LL dep[N],fa[N],siz[N],son[N],top[N],id[N];
void dfs1(LL x,LL pre)
{
	dep[x]=dep[pre]+1;
	fa[x]=pre;
	siz[x]=1;
	for(LL i=link[x];i;i=e[i].next)
	{
		LL y=e[i].y;
		if(y==pre) continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]])
		{
			son[x]=y;
		}
	}
}
LL idx;
void dfs2(LL x,LL topth)
{
	id[x]=++idx;
	top[x]=topth;
	if(!son[x]) return;
	dfs2(son[x],topth);
	for(LL i=link[x];i;i=e[i].next)
	{
		LL y=e[i].y;
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
LL Min[N<<2];
void pushup(LL k)
{
	Min[k]=min(Min[k<<1],Min[k<<1|1]);
}
void build(LL k,LL l,LL r)
{
	if(l==r) 
	{
		Min[k]=w[l];
		return;
	}
	LL mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
multiset<LL> S[N];
void construct()
{
	t=0;
	memset(link,0,sizeof(link));
	for(LL i=1;i<=cnt;i++)
	{
		LL x=++Size;
		for(LL j=0;j<Dcc[i].size();j++)
		{
			LL y=Dcc[i][j];
			add(x,y);
			add(y,x);
		}
	}
	dfs1(1,0);
	dfs2(1,1);
	for(LL i=1;i<=n;i++)
	w[id[i]]=a[i];
	for(LL x=n+1;x<=Size;x++)
	{
		for(LL i=link[x];i;i=e[i].next)
		{
			LL y=e[i].y;
			if(y==fa[x]) continue;
			S[x].insert(w[id[y]]);
		}
		if(S[x].empty()) w[id[x]]=INF;
		else w[id[x]]=*S[x].begin();
	}
	build(1,1,Size);
}
void update(LL k,LL l,LL r,LL x,LL v)
{
	if(l==r&&l==x)
	{
		Min[k]=v;
		return;
	}
	LL mid=(l+r)>>1;
	if(x<=mid) update(k<<1,l,mid,x,v);
	else update(k<<1|1,mid+1,r,x,v);
	pushup(k);
}
LL query(LL k,LL l,LL r,LL L,LL R)
{
	if(L<=l&&r<=R) return Min[k];
	LL mid=(l+r)>>1;
	LL res=INF;
	if(L<=mid) res=min(res,query(k<<1,l,mid,L,R));
	if(R>mid) res=min(res,query(k<<1|1,mid+1,r,L,R));
	return res;
}
void change(LL x,LL v)
{
	LL f=fa[x];
	if(f!=0)
	{
		S[f].erase(S[f].find(w[id[x]]));
		S[f].insert(v);
		w[id[f]]=*S[f].begin();
		update(1,1,Size,id[f],w[id[f]]);
	}
	w[id[x]]=v;
	update(1,1,Size,id[x],w[id[x]]);
}
LL query_chain(LL x,LL y)
{
	LL res=INF;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=min(res,query(1,1,Size,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);

	res=min(res,query(1,1,Size,id[x],id[y]));
	if(x>n)
	res=min(res,w[id[fa[x]]]);
	return res;
}
int main()
{
	n=read();
	m=read();
	q=read();
	for(LL i=1;i<=n;i++)
	a[i]=read();
	for(LL i=1;i<=m;i++)
	{
		LL x,y;
		x=read();
		y=read();
		add(x,y);
		add(y,x);
	}
	root=1;
	Size=n;
	tarjan(1);
	construct();
	while(q--)
	{
		char opt[3];
		LL x,y;
		scanf("%s",opt);
		x=read();
		y=read();
		if(opt[0]=='C') change(x,y);
		else printf("%d\n",query_chain(x,y));
	}
	return 0;
}

这样就行了