P4145 上帝造题的七分钟 2 / 花神游历各国（并查集+树状数组）

目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

有 \(n\) 个数

接下来 $m$ 行每行三个整数 k l r。

• $k=0$ 表示给 $[l,r]$ 中的每个数开平方（下取整）。

• $k=1$ 表示询问 $[l,r]$ 中各个数的和。

State

\(1<=n<=10^5\)

\(1<=a[i]<=10^{12}\)

\(1<=l<=r<=n\)

Input

?

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

Output

19
7
6

Solution

题目当中的修改有一个特点，就是一直单调修改，也就是覆盖；这样可以考虑构造一个连通图，起初每一个数都是孤点，只有当其变为 \(1\) 时，需要将这个点略过，由于每一次都要找到下一次需要更改的点，所以并不需要关注前驱，只要关注后继就可以

虽然 \(10^{12}\) 数据范围很大，但是开根号 \(6\) 次就可以将数变为 \(1\)，而变为 \(1\) 的数就不需要改变了，也就保证了复杂度；

Code

const int N = 1e5 + 5;

    ll n, m, _;
    int i, j, k;
    ll a[N];

ll c[N];
void add(int x, ll eva)
{
    for(;x <= n; x += lowbit(x)){
        c[x] += eva;
    }
    return void();
}

ll ask(int x)
{
    ll ans = 0;
    for(;x ; x -= lowbit(x)){
        ans += c[x];
    }
    return ans;
}

int fa[N];
int Find(int x)
{
    if(x == fa[x]) return x;
    else{
        int nx = Find(fa[x]);
        return fa[x] = nx;
    }
}

signed main()
{
    //IOS;
    while(~ sd(n)){
        rep(i, 1, n + 1) fa[i] = i;
        rep(i, 1, n) sll(a[i]), add(i, a[i]);
        sd(m);
        rep(k, 1, m){
            int opt, x, y;
            sddd(opt, x, y);
            if(x > y) swap(x, y);
            if(opt == 1) pll(ask(y) - ask(x - 1));
            else{
                int now = Find(x);
                while(now <= y){
                    ll change = (ll)sqrt(a[now]) - a[now];
                    add(now, change);
                    a[now] = sqrt(a[now]);
                    if(a[now] == 1) fa[now] = Find(now + 1);
                    now = Find(now + 1);
                }
            }
        }
    }
    //PAUSE;
    return 0;
}