自动搬运

查看原文

来自洛谷，原作者为

	suxxsfe 我道歉，我忏悔，我是垃圾，我将彻底失败

搬运于2025-08-24 22:22:53，当前版本为作者最后更新于2020-08-14 10:50:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在我的 blog 中查看：https://www.cnblogs.com/suxxsfe/p/13500935.html

http://uoj.ac/problem/274
https://www.luogu.com.cn/problem/P6664

根据题目的条件（温度各不相同）和要求（温度排序后字典序最小），容易推出，实际上每次询问就是要求两个端点之间最低温度最高的，同时不存在环（就是在最低温最高基础上最短）的一条路径

其实和 水管局长 那题比较像，有连边操作，想到用 lct 维护，对于每个新加入的边：

• 如果它两端点还没有联通，直接连边即可。
• 如果两端点已经联通了，求出两端点之间路径中最低温度，如果新边的温度低于此值，不用管（因为不存在删边，所以不可能走到这条新边）。否则，就把原路径中最低温的边断开，并连接新边。

这样做的正确性也就比较显然，其实就是维护一个最大生成树

还需要一个技巧来维护边的信息，就是为每一个边新建一个虚拟节点，权值（在这里是长度）为边权。
然后连边时就用这个虚拟节点和它两个端点相连，端点（实际节点）的点权为 $0$，就能正常维护信息了。
这样修改操作就把那条边的虚拟节点伸展到 lct 的根，然后更新。
查询先看是否联通，如果联通就把那条路径 split 出来，查询长度和。

为了方便找路径中最低温的边是哪个，节点结构体中的 min 其实是最低温边的标号。

代码，洛谷UOJ都能过，而且似乎并不像网上博客说的一样需要刻意卡常

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
#define N 100005
#define M 300005
int n,m;
int tem[M];
struct tr{
	tr *son[2],*fa;
	int tag;
	int sumlen,len,min,thismin;
}*null,*pos[N+M],dizhi[N+M];
int U[M],V[M];
#define ident(tree,fa) (fa->son[1]==tree)
#define notroot(tree) (tree->fa->son[0]==tree||tree->fa->son[1]==tree)
#define min(x,y) (tem[x]<tem[y]?x:y)
inline void connect(tr *tree,tr *fa,int k){fa->son[k]=tree;tree->fa=fa;}
inline void pushdown(tr *tree){
	if(!tree->tag) return;
	tree->son[0]->tag^=1;tree->son[1]->tag^=1;
	std::swap(tree->son[0],tree->son[1]);
	tree->tag=0;
}
inline void pushup(tr *tree){
	tree->sumlen=tree->len+tree->son[0]->sumlen+tree->son[1]->sumlen;
	tree->min=min(tree->thismin,min(tree->son[0]->min,tree->son[1]->min));
}
inline void rotate(tr *tree){
	tr *fa=tree->fa,*faa=fa->fa;
	pushdown(fa);pushdown(tree);
	int k=ident(tree,fa);
	connect(tree->son[k^1],fa,k);
	tree->fa=faa;
	if(notroot(fa)) faa->son[ident(fa,faa)]=tree;
	connect(fa,tree,k^1);
	pushup(fa);pushup(tree);
}
inline void splay(reg tr *tree){
	reg tr *fa,*faa;
	while(notroot(tree)){
		fa=tree->fa;faa=fa->fa;
		if(notroot(fa)) rotate(ident(tree,fa)^ident(fa,faa)?tree:fa);
		rotate(tree);
	}
}
inline void access(reg tr *x){
	for(reg tr *lastx=null;x!=null;lastx=x,x=x->fa){
		pushdown(x);
		splay(x);
		x->son[1]=lastx;pushup(x);
	}
}
inline void makeroot(tr *x){
	access(x);
	splay(x);
	x->tag^=1;
}
inline tr *findroot(tr *x){
	access(x);splay(x);
	pushdown(x);
	while(x->son[0]!=null) x=x->son[0],pushdown(x);
	splay(x);
	return x;
}
inline int linked(tr *x,tr *y){
	makeroot(x);
	return findroot(y)==x;
}
inline void split(tr *x,tr *y){
	makeroot(x);
	access(y);splay(y);
}
inline void link(tr *x,tr *y){
    makeroot(x);
	if(findroot(y)!=x) x->fa=y;
}
inline void cut(tr *x,tr *y){
    split(x,y);
    x->fa=y->son[0]=null;
}
inline void init(){
	null=&dizhi[0];
	for(reg int i=1;i<=n;i++){
		pos[i]=&dizhi[i];
		dizhi[i].son[0]=dizhi[i].son[1]=dizhi[i].fa=null;
	}
}
inline void creat(int i,int l){
	pos[i]=&dizhi[i];
	dizhi[i].son[0]=dizhi[i].son[1]=dizhi[i].fa=null;
	dizhi[i].min=dizhi[i].thismin=i-n;
	dizhi[i].sumlen=dizhi[i].len=l;
}
int main(){
	n=read();m=read();
	init();
	tem[0]=2e9;
	char c;int id,u,v,k;
	while(m--){
		c=getchar();
		while(c!='f'&&c!='c'&&c!='m') c=getchar();
		if(c=='f'){
			id=read()+1+n;u=read()+1;v=read()+1;tem[id-n]=read();k=read();
			creat(id,k);
			if(linked(pos[u],pos[v])){
				split(pos[u],pos[v]);
				if(tem[pos[v]->min]>=tem[id-n]) continue;
				int tmp=pos[v]->min;
				cut(pos[tmp+n],pos[U[tmp]]);cut(pos[tmp+n],pos[V[tmp]]);
			}
			link(pos[id],pos[u]),link(pos[id],pos[v]);
			U[id-n]=u;V[id-n]=v;
		}
		else if(c=='c'){
			id=read()+1+n;k=read();
			splay(pos[id]);
			pos[id]->len=k;
			pushup(pos[id]);
		}
		else{
			u=read()+1;v=read()+1;
			if(!linked(pos[u],pos[v])) puts("-1");
			else{
				split(pos[u],pos[v]);
				printf("%d\n",pos[v]->sumlen);
			}
		}
	}
	return 0;
}