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

Milk_snake · 2026-10-20 15:10:38 · 题解

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

简要题意：

给你一个长度为 n 的排列，请你求出 \displaystyle\sum_{l = 1} ^ n \sum_{r = l}^ n f(l, r) 的值。

其中 f(l,r) 表示一段 l 到 r 的序列，将该段序列排序之后划分成若干个连续段，使得每一段内部的数都是连续的正整数时，最长段的长度。

思路：

普通暴力肯定超时，注意到 n \le 3000，O(n^2) 可以过去。

暴力枚举 l 和 r，对于每次新加入的下标 r，我们可以用并查集维护当前所有连续数的集合，将相邻两个数尝试加入 a_r 所在的集合中，然后实时跟新最长段长度 maxn，最后将所有的 maxn 全部加起来就可以了。

CODE：

#include<bits/stdc++.h>
using namespace std;
int n,maxn;
long long ans;
int a[3005],fa[3005],siz[3005];
int find(int x){
    if(!fa[x]||x<1||x>n){
        return 0;
    }
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void join(int x,int y){
    x=find(x);
    y=find(y);
    if(x&&y){
        fa[x]=y;
        siz[y]+=siz[x];
        maxn=max(maxn,siz[y]);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int l=1;l<=n;l++){
        memset(fa,0,sizeof(fa));
        memset(siz,0,sizeof(siz));
        maxn=1;
        for(int r=l;r<=n;r++){
            fa[a[r]]=a[r];
            siz[a[r]]=1;
            join(a[r]+1,a[r]);
            join(a[r]-1,a[r]);
            ans+=maxn;
        }
    }
    cout<<ans;
    return 0;
}