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

· · 题解

题目大意

找出所有子数组内排序后的最长连续正整数的长度之和。

说人话：对每个子数组，只取其中的数值，求数值上最长的一段连续正整数长度，最后把所有子数组的这个长度加起来。

然后题目还保证了排列，所以不需要我们伟大的哈希表。

思路

我们可以把连续正整数看成一个集合，就可以发现，加入一个元素可能这些集合出现三种结果：

我们发现其实所有操作都可以看成第三种操作，第一种操作可以看成它本身和空气合并，第二种可以看成它本身和连续正整数集合合并。

说到集合的合并，就要上并查集。

:::info[并查集大学习]

简讲

并查集，可以在几乎线性甚至常数的时间复杂度下完成：合并集合、查询两个元素的连通性、甚至这个集合的大小。

方法

先假设集合是一棵树，而多个集合则可以变成森林，我们就可以：

  1. 把合并集合转化为合并并树；

  2. 把查询连通性转化成查询是否是同一棵树，再变成查询根是否相等；

  3. 把集合大小看成根的子树大小。

是不是非常的简单易懂，我们再拆解一些我们需要的东西：

而并树这个操作，可以把一棵树的根变成另一棵树的子节点，非常简单。

于是，你获得了 O(n) 的常规并查集。

然后我们自己发明了路径压缩和大小交换。

路径压缩

我们查询根的最终原因其实还是要查询元素连通性，并不需要一些树的基本结构，我们甚至可以造一个美丽的菊花（绝对不是想让 SPFA TLE），而造菊花可以让我们的查询根变成完美的 O(1)，但是在哪里可以顺便造个菊花呢？没错！可以在查询根的时候顺便造一个。

这就是路径压缩。

按秩排序（大小交换）

这个东西就很好理解了，就比如说：你要把一大一小的箱子推到一块，你会推大的还是小的？显然是个人类都会选择推小的，这就是按秩排序（大小交换），当你合并树的时候，要把小数接到大树上，这样才会更快！

最终时间复杂度 O(\alpha(n))，近似常数。

而我们观察集合的合并条件，发现也就是有一个包含 p_{x} \pm 1 的集合可以和包含 p_{x} 的集合合并，而我们可以固定左端点，右移右端点，并且我们发现每次只会更新 p_{r}，所以每次让右端点判断是否可以合并更多集合，就很简单了。

注意点：一定要判断 p_{r} \pm 1 是否存在，以及查找子树大小的地方得先找根再查询，否则你会直接 WA 飞。

记住查询的一定是 p_{r} 不是 r！

#include <bits/stdc++.h>
using namespace std;
class union_find//并查集
{
    private:
        unsigned N;
        std::vector <unsigned> fa,sz;
        unsigned getfa(unsigned x)//迭代找根
        {
            if(x>N||x==0) return x;
            unsigned root=x;
            while(fa[root]!=root) root=fa[root];
            while(fa[x]!=x)
            {
                unsigned fa_x=fa[x];
                fa[x]=root;
                x=fa_x;
            }
            return root;
        }
    public:
        union_find(unsigned n)//初始构造
        {
            N=n;
            fa.resize(n+1);
            sz.resize(n+1);
            for(unsigned i=1;i<=n;i++) fa[i]=i;
            for(unsigned i=1;i<=n;i++) sz[i]=1;
        };
        bool merge(unsigned a,unsigned b)//并集
        {
            if(a>N||b>N||a==0||b==0) return false;
            a=getfa(a);b=getfa(b);
            if(a==b) return false;
            if(sz[a]>sz[b]) swap(a,b);
            fa[a]=b;
            sz[b]+=sz[a];//增加b的子树大小
            return true;
        }
        bool check(unsigned a,unsigned b)//检查是否在一起，虽然没用到
        {
            if(a>N||b>N||a==0||b==0) return false;
            return getfa(a)==getfa(b);
        }
        unsigned size(unsigned x)//返回集合大小
        {
            if(x>N||x==0) return 0;
            return sz[getfa(x)];//一定要找到根了再查询子树大小！
        }
};
unsigned n,now,p[3002];
bool f[3002];
long long unsigned ans;
int main()
{
    scanf("%u",&n);
    for(unsigned i=1;i<=n;i++) scanf("%u",&p[i]);
    for(unsigned l=1;l<=n;l++)
    {
        memset(f,false,sizeof(f));
        union_find uf(n);
        now=0;
        for(unsigned r=l;r<=n;r++)
        {
            f[p[r]]=true;
            if(f[p[r]-1]) uf.merge(p[r]-1,p[r]);//必须出现过才能合并（并且p[r]=1的时候还可以额外排除掉p[r]-1=0的情况）
            if(f[p[r]+1]) uf.merge(p[r]+1,p[r]);//同样（并且p[r]=n的时候也可以排除掉p[r]+1=n+1的情况）
            now=max(now,uf.size(p[r]));
            ans+=now;
        }
    }
    printf("%llu",ans);
    return 0;
}

时间复杂度 O(n^{2}\alpha(n))，其中 n^{2} 来自枚举 l,r。

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