题解：P17720 「FunMusic OI 1C」旋律 / Melody

_hxy_ · 2026-10-20 11:36:26 · 题解

思路解析：

诈骗题，诈骗我。不难发现暴力枚举左右端点是可以的，怎么不用循环求最长连续段呢？首先，在右端点往右移的时候这个值不会下降，因为原来的最长串只会增长，不会缩短。用并查集维护每个值之间的连边，用 sz 维护一下联通块大小，做完了。

代码展示：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3100;
int fa[N],sz[N],a[N];
int n,ans,cnt;
int yyc(int x){
    if((!fa[x])||x==0||x==n+1) return 0;//得出现
    return fa[x]==x?x:fa[x]=yyc(fa[x]);//路径压缩
}

void hb(int x,int y){
    x=yyc(x);y=yyc(y);
    if(x&&y){
        sz[y]+=sz[x];//大小相加
        fa[x]=y;//合并
        cnt=max(cnt,sz[y]);//取max
    }
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];//输入
    for(int i=1;i<=n;i++){memset(fa,0,sizeof(fa));memset(sz,0,sizeof(sz));cnt=1;//不清空，爆零两行泪
        for(int j=i;j<=n;j++){//枚举右端点
            fa[a[j]]=a[j];sz[a[j]]=1LL;//标记为出现，大小为1
            hb(a[j]+1,a[j]);hb(a[j]-1,a[j]);//合并
            ans+=cnt;//累加答案
        }
    }
    cout<<ans;//输出
    return 0;
}