[UOJ274] P6664 温暖会指引我们前行

suxxsfe · 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;
}