题解 | 区间根号与区间求和

由于sqrt操作会让数字极速降低，很快会降低到1，那么维护区间和以及区间最大值，最大值等于1的区间就不用管了。维护这两个信息可以用线段树或者分块实现，这里实现了一个分块。

对于修改操作，直接暴力枚举所有块，如果块的最大值比1大，直接将这个块的所有元素取根号。

对于查询操作，我们需要维护一个块的和信息。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
const int N = 100001;
const int M = 100001;
const int MOD = 1e9+7;
class SequenceBlock {
public:
    vector<int> bi,bl,br;
    int blen,bnum;
    vector<int> arr,sum,maxv;
    int n;
    void init(int n) {
        blen = sqrt(n);
        bnum = (n + blen - 1) / blen;
        bi.resize(n);bl.resize(bnum);br.resize(bnum);
        sum.resize(bnum);maxv.resize(bnum);
        for (int i = 0; i < n; i ++) {
            bi[i] = i / blen;
            sum[bi[i]] += arr[i];
            maxv[bi[i]] = max(maxv[bi[i]], arr[i]);
        }
        for (int i = 0; i < bnum; i++) {
            bl[i] = i * blen;
            br[i] = min((i + 1) * blen - 1, n - 1);
        }
    }
    SequenceBlock(int n) {
        this->n = n;
        init(n);
    }
    SequenceBlock(vector<int>& arr) {
        this->n = arr.size();
        this-> arr = arr;
        init(n);
    }
    void rangeUpdate(int l,int r) {
        auto forceUpdate = [&](int l,int r) {
            for (int i = l; i <= r; i++) {
                arr[i] = sqrt(arr[i]);
            }
            int bid = bi[l];
            //[l,r]不一定全。
            sum[bid] = maxv[bid] = 0;
            for (int i = bl[bid]; i <= br[bid]; i ++) {
                sum[bid] += arr[i];
                maxv[bid] = max(maxv[bid], arr[i]);
            }
        };
        if (bi[l] == bi[r]) {
            forceUpdate(l,r);
            return;
        }
        forceUpdate(l,br[bi[l]]);
        forceUpdate(bl[bi[r]],r);
        for (int i = bi[l] + 1; i < bi[r]; i++) {
            if (maxv[i] > 1) forceUpdate(bl[i],br[i]);
        }

    }
    int rangeQuery(int l,int r) {
        auto forceQuery = [&](int l,int r) {
            int s = 0;
            for (int i = l; i <= r; i++) {
                s += arr[i];
            }
            return s;
        };
        if (bi[l] == bi[r]) {
            return forceQuery(l,r);
        }
        //暴力查询左右散块，中间的块直接累加和。
        int res = forceQuery(l,br[bi[l]]) + forceQuery(bl[bi[r]],r);
        //查询中间块
        for (int i = bi[l] + 1; i < bi[r]; i++) {
            res += sum[i];
        }
        return res;
    }

};

void solve() {
    int n,q; cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    SequenceBlock sb(a);

    while (q--) {
        int op,l,r; cin >> op >> l >> r;
        if (op == 1) {
            sb.rangeUpdate(l - 1,r - 1);
        }else {
            cout << sb.rangeQuery(l - 1,r - 1) << endl;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}