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

fdd1_ · 2026-10-20 13:27:42 · 题解

同学都在写题解，我也来一个。

题目大意

定义 f_{i,j} 为区间 [i,j] 之间排序之后的最长连续段，求 \displaystyle \sum_{l = 1} ^ n \sum_{r = l}^ n f(l, r) 的值。

思路解析

注意到数据范围 n \le 3000。

于是我们可以枚举左右边界，但是怎么求最长连续段呢？

思考……

我们可以用并查集维护，对于每一个数 x，我们可以让他与 x-1,x+1 合并，并求出每块大小，与答案取最大值。

代码展示

#include<bits/stdc++.h>
using namespace std;
int n;
int a[3010]; 
int fa[3010];
int sz[3010];
int maxx;
long long ans;
int getfa(int x){
    if(fa[x]==0){
        return 0;
    }
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y){
    x=getfa(x);
    y=getfa(y);
    if(x!=y&&x&&y){
        sz[y]+=sz[x];
        fa[x]=y;
        maxx=max(maxx,sz[y]);//答案取 max 
    }
}
int main(){
    ios::sync_with_stdio(0);
    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++){
        for(int j=1;j<=n;j++){
            fa[j]=0;
            sz[j]=0;//初始化 
        }
        maxx=1;
        for(int j=i;j<=n;j++){
            fa[a[j]]=a[j];
            sz[a[j]]=1;//初始化*2 
            merge(a[j]-1,a[j]);
            merge(a[j]+1,a[j]);//合并 
            ans+=maxx; //+答案 
        }
    }
    cout<<ans;
    return 0;
}

十年 OI 一场空，不开 long long 见祖宗。

谢谢观看。