题目链接

https://ac.nowcoder.com/acm/contest/8564/I

解题思路

也不知道大佬是怎么想出来的，要用最小生成树。

一大佬题解：
给你的序列a是任意的, 我们就人为添加一个 点(n+1) 且 a[n+1] = 0
每次操作 l, r, 可以使得 a[l] 和 a[r + 1] 变得相同
最终目标是所有点都可以和 a[n+1] 相同变成 0
这不就是最小生成树吗?

另一大佬题解

如果有人不知道最小生成树（比如我）就看看这个吧：
最小生成树讲解

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;

struct edge
{
    int u,v;
    ll w;
}e[N<<1];
int n,m,cnt,fa[N];
ll ans;

bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

int main()
{
    cin>>n>>m; ++n;//勿忘++
    for(int i=1;i<=n;i++) fa[i]=i;//勿忘初始化
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int rx=find(e[i].u),ry=find(e[i].v+1);//勿忘+1
        if(rx!=ry) ans+=e[i].w,fa[rx]=ry,++cnt;
    }
    cout<<(cnt==n-1?ans:-1)<<endl;
}

总结

WTCL。
不知道为什么，看完这个题的题解，我想到了个题。
修改数组（蓝桥）