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

Witness_sc · 2026-10-19 20:16:27 · 题解

思路

考虑枚举区间的左端点 l，并不断向右扩展右端点 r，逐步加入新的数 a_r。

为了维护区间内最长的连续整数段，可以使用并查集。每个数初始时单独属于一个集合，集合大小为 1。当加入 a_r 时，如果 a_r-1 或 a_r+1 已经出现，就将 a_r 与对应数字所在的集合合并，使每个集合都表示一段连续的整数。

每次合并后，维护当前最大的集合大小，即可得到当前区间的 f(l,r)。将所有区间的结果累加，就能得到最终答案。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010;
int n;
int a[N],fa[N],sz[N],vis[N];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        fa[x]=y;
        sz[y]+=sz[x];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int l=1;l<=n;l++){
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            fa[i]=i;
            sz[i]=1;
        }
        int mx=0;
        for(int r=l;r<=n;r++){
            int x=a[r];
            vis[x]=1;
            if(x>1 && vis[x-1]){
                merge(x,x-1);
            }
            if(x<n && vis[x+1]){
                merge(x,x+1);
            }
            mx=max(mx,sz[find(x)]);
            ans+=mx;
        }
    }
    cout<<ans<<endl;
    return 0;
}