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

sunpengyu · 2026-10-20 14:20:26 · 题解

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

题目大意

给定一个长度为 n 的排列 p。 对于每一个子区间 [l,r]，取出区间内所有数，将它们按值域划分成若干段值域连续的块。定义 f(l,r) 为这些块中最大块的长度。 求：\sum_{l=1}^n\sum_{r=l}^n f(l,r)

数据范围：1\le n \le 3000。

解法

看一眼标签，发现是并查集，那么考虑怎么用并查集维护。根据思考，我们可以用并查集维护值域，合并的条件也很简单，就是当前序列里有和新加进来的数差一的值。同时我们可以用一个数组记录每个连通块的大小，最大的连通块的大小就是这一段区间的答案。

在区间更新的时候显然得到：最大值是原最大值和更新块的值的更大的那一个。

::::success[AC code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e3+5;
int n,a[N],ans,f[N],vis[N],tot[N];
void init(){
    for(int i=1;i<=n;i++){
        f[i]=i;
        tot[i]=1;
    }
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    f[x]=y;
    tot[y]+=tot[x];
    tot[x]=0;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        init();
        memset(vis,0,sizeof(vis));
        int mx=0;
        for(int j=i;j<=n;j++){
            vis[a[j]]=1;
            if(vis[a[j]-1]) merge(a[j]-1,a[j]);
            if(vis[a[j]+1]) merge(a[j]+1,a[j]);
            int now=tot[find(a[j])];
            if(now>mx) mx=now;
            ans+=mx;
        }
    }
    cout<<ans;
    return 0;
}

::::

OK现在来解释一下代码。