代码

暴力（TLE）

#include <bits/stdc++.h>

#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], op;

int work(int &x, int k) {
    while (k-- && x != round(sqrt(x) * 10.)) x = round(sqrt(x) * 10.);
    return x;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], a[0] += a[i];
    while (m--) {
        cin >> op;
        if (op == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            for (int i = x; i <= y; ++i) {
                a[0] -= a[i] - work(a[i], k);
            }
        } else {
            cout << a[0] << endl;
        }
    }
    return 0;
}

stl做法

#include <bits/stdc++.h>

#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, op, ans, x, y, k;
map<int, int> a;

signed main() {
    cin >> n >> m, a[-1] = 1, a[n + 1] = 1;
    for (int i = 1, ls; i <= n; cin >> ls, a[i] = ls, ans += ls, i++);
    while (m-- && cin >> op) {
        if (op == 1) {
            cin >> x >> y >> k;
            for (auto item = a.lower_bound(x); item->first <= y; item++) {
                int &it = item->second, res = 0, i = k;
                while (i--) {
                    res = round(sqrt(it) * 10.);
                    if (res == it) {
                        a.erase(item--);
                        break;
                    }
                    ans += res - it, it = res;
                }
            }
        } else
            cout << ans << endl;
    }
    return 0;
}