题解 P1840 【Color the Axis_NOI导刊2011提高（05）】

木木！ · 2019-08-09 09:20:36 · 题解

我是来给并查集大佬补时间复杂度证明的QwQ。

设势能函数\Phi(s)=\text{s中并查集个数}，易知在一开始\Phi(s)=n。

而每次操作，如果一下子跳不到r的话，会执行合并，将并查集数量-1，势能函数就减少了1。则，该次多余跳+合并不消耗时间。

因此，每次修改的时间复杂度是\Theta(1)。

由于一开始\Phi(s)=n，所以必须得在程序开始时额外花费\Theta(n)的时间提高势能函数。

所以，最终时间复杂度为\Theta(n+m)。

附AC代码：

#include <cstdio>
using namespace std;

int st[200005];

int getfa(int x)
{
    return x==st[x]?x:st[x]=getfa(st[x]);
}

void unio(int a,int b)
{
    st[getfa(b)] = getfa(a);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    int blkn = n;   
    for(int i=1; i<=n+1; ++i)
    {
        st[i] = i;
    }
    for(int i=1; i<=m; ++i)
    {
        int li,ri;
        scanf("%d%d",&li,&ri);

        int t = getfa(li);
        while(t<=ri)
        {
            unio(t+1,t);
            t = getfa(t);
            --blkn;
        }

        printf("%d\n",blkn);
    }
}

（线段树的题怎么能用线段树做呢）