并查集.md

并查集

---

鸡格线

题意： 有一个长度为n的数组，需要支持以下两种操作：

1. 输入l, r, k, 对区间[l, r]中所有数字执行ai=f(ai)操作k次， $$ f_(x)=round(10\sqrt{x}) $$ round为四舍五入函数。

2. 输出当前数组所有数字的和。

解题思路： 手算一下f函数，可以发现任意一个数字在f的重复作用下会稳定在特定的数字上。

==没有规律怎么做题？==

列出方程： $$ x=round(10\sqrt{x}) $$ 可以解得x=90或100(当然不是手算啦)。这启示我们跳过对一些不会再改变的数字的操作来降低复杂度。

代码：

int get(int x)
{
    if(x==fa[x])
        return x;
    return fa[x]=get(fa[x]);
}
void change(int l,int r,int k)
{
    for(int i=get(l);i<=r;i=get(i+1)){
        for(int j=1;j<=k;j++){
            sum+=round(10.0*sqrt(a[i]))-a[i];	//这种要学一下的
            a[i]=round(10.0*sqrt(a[i]));
            if (a[i] == round(10.0 * sqrt(a[i]))) {
                fa[i] = get(i + 1);
                break;
            }
        }
    }
    return;
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n+1;i++)	//注意这里初始化的范围，要到n+1
        fa[i]=i;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        if(a[i]==round(10.0*sqrt(a[i])))
            fa[i]=i+1;
    }
    
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,k;
            cin>>l>>r>>k;
            change(l,r,k);
        }
        else{
            cout<<sum<<'\n';
        }
    }
}