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

Kaede219 · 2026-10-19 18:20:07 · 题解

思路

我们观察到题目中的 n \le 3000，这启示我们暴力维护左右端点是可行的。

我们发现，区间 [l,r+1] 的结果一定大于等于区间 [l,r] 的结果。所以可以考虑在拓展右端点的同时考虑合并。

由于题目中的关系是无向且具有传递性的，所以我们可以考虑使用并查集来维护连通块大小，并在合并过程中求出当前时刻连通块大小的最大值。

注意在每次左端点移动的时候要清空并查集所维护的信息。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3100;
int fa[maxn];
int sz[maxn];
int n;
int getfa(int x)
{
    if((!fa[x])||x==0||x==n+1)//该数字不在此区间中
        return -1;
    return fa[x]==x?x:fa[x]=getfa(fa[x]);//路径压缩
}
int ma;
void merge(int x,int y)
{
    x=getfa(x);
    y=getfa(y);
    if(x!=-1&&y!=-1)
    {
        fa[x]=y;
        sz[y]+=sz[x];//合并连通块大小
        ma=max(ma,sz[y]);//取连通块大小最大值
    }
}
int a[maxn];
int ans;
signed 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(sz,0,sizeof(sz));//清空维护信息
        ma=1;
        for (int r=l;r<=n;r++)
        {
            fa[a[r]]=a[r];//并查集初始化
            sz[a[r]]=1;//连通块大小初始化
            merge(a[r]+1,a[r]);//合并
            merge(a[r]-1,a[r]);//合并
            ans+=ma;
        }
    }
    cout<<ans;
}