Jennie

用splay维护编号就可以了

如果我们要反转[l,r]，那么这个l，就是区间第l个数

然后splay的中序遍历就是整个区间，

那么显然的就是，我们只要找到第l个数就可以了

也就是所谓的按照排名找数。

找到之后，为了维护中序遍历，把l转到根，r转到l右边（也只能是右边了）

然后根r的左儿子打一个标记就可以了，

就像线段树一样，记得下传并且交换左右子树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
const int maxn=100005;
int fa[maxn][20];
int ma[maxn][20];
int cmax[maxn][20];
struct ed{
    int to;
    int ne;
    int f;
    int v;
}org[maxn<<2],tru[maxn<<2];
int n,m;
int ff[maxn];
bool cmp(ed x,ed y){
    return x.v<y.v;
}
int find(int x){
    return ff[x]==x?ff[x]:ff[x]=find(ff[x]);
}
int head[maxn];
int p;
void add(int f,int to,int ne){
    tru[++p].to=to;
    tru[p].ne=head[f];
    head[f]=p;
    tru[p].v=ne;
}
int dep[maxn];
void dfs(int rt,int f){
    dep[rt]=dep[f]+1;
    int x=rt;
    for(int i=1;i;++i){
        if(dep[rt]<(1<<i)) break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
        ma[x][i]=max(ma[x][i-1],ma[fa[x][i-1]][i-1]);
        if(ma[x][i-1]==ma[fa[x][i-1]][i-1])
            cmax[x][i]=max(cmax[x][i-1],cmax[fa[x][i-1]][i-1]);
        else{
            cmax[x][i]=max(min(ma[x][i-1],ma[fa[x][i-1]][i-1]),
            max(cmax[x][i-1],cmax[fa[x][i-1]][i-1]));
        }   
    }
    for(int i=head[x];i;i=tru[i].ne){
        int v=tru[i].to;
        if(v!=f){
            fa[v][0]=rt;
            ma[v][0]=tru[i].v;
            cmax[v][0]=-1;
            dfs(v,rt);
        }
    }
}
int up=99999999;
int lca(int l,int r){
    if(dep[l]<dep[r]) swap(l,r);
    int k=dep[l]-dep[r];
    for(int i=0;i<=17;++i){
        if(k&(1<<i)) l=fa[l][i];
    }
    if(l==r) return l;
    for(int i=17;i>=0;--i){
        if(fa[l][i]!=fa[r][i]){
            l=fa[l][i];
            r=fa[r][i];
        }
    }
    return fa[l][0];
}
int vis[1000001];
void work(int f,int ro,int v){
    int maxx=0;int cmaxx=0;
    int k=dep[f]-dep[ro];
    for(int i=0;i<=17;++i){
        if((k)&(1<<i)){
            cmaxx=max(cmaxx,cmax[f][i]);
            if(ma[f][i]>maxx){
                cmaxx=max(maxx,cmaxx);
                maxx=ma[f][i];
            }
            f=fa[f][i];
        }
    }
    if(maxx==v){
        up=min(up,v-cmaxx);
    }else{
        up=min(up,v-maxx);
    }
}
int sum;
signed main(){
    read(n);read(m);
    for(int i=1;i<=m;++i){
        read(org[i].f);read(org[i].to);
        read(org[i].v);
    }
    for(int i=1;i<=n;++i)
        ff[i]=i;
    sort(org+1,org+m+1,cmp);
    int cnt=0;
    for(int i=1;i<=m;++i){
        int x=find(org[i].f);
        int y=find(org[i].to);
        if(x==y) continue;
        vis[i]=1;
        ff[x]=y;
        cnt++;
        add(org[i].f,org[i].to,org[i].v);
        sum+=org[i].v;
        add(org[i].to,org[i].f,org[i].v);
        if(cnt==n-1) break;
    }
    dfs(1,0);
    for(int i=1;i<=m;++i){
        if(vis[i]) continue;
        int l=org[i].f;int r=org[i].to;
        int ance=lca(l,r);
        work(l,ance,org[i].v);
        work(r,ance,org[i].v);
    }
    cout<<sum+up;
    return 0;
}