8466.cpp

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005, maxq = 20005, step = 500, maxb = step * 2 + 5;
const long long inf = 1e18;
int n, q;
long long a[maxn];
int type[maxq], l[maxq], r[maxq], x[maxq];

int order[maxn];
int id[maxn], block_start[maxb], sz[maxb];
long long _min[maxb], _max[maxb], offset[maxb], sum[maxb];
int cnt_min[maxb], cnt_max[maxb];

void change(long long a, int block) {
    if (a < _min[block]) _min[block] = a, cnt_min[block] = 1;
    else if (a == _min[block]) ++cnt_min[block];
    if (a > _max[block]) _max[block] = a, cnt_max[block] = 1;
    else if (a == _max[block]) ++cnt_max[block];
}

long long get_sum(int block) {
    if (_max[block] - _min[block] > 1) return sum[block] + offset[block] * sz[block];
    if (_max[block] - _min[block] == 1) return _min[block] * cnt_min[block] + _max[block] * cnt_max[block] + offset[block] * sz[block];
    return _min[block] * cnt_min[block] + offset[block] * sz[block];
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int ntest;
    cin >> ntest;
    while (ntest--) {
        cin >> n >> q;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= q; ++i) {
            cin >> type[i] >> l[i] >> r[i];
            if (type[i] == 3) cin >> x[i];
        }
        for (int st = 1; st <= q; st += step) {
            memset(id, 0, sizeof id);
            memset(sum, 0, sizeof sum);
            memset(offset, 0, sizeof offset);

            int en = min(q, st + step - 1);
            for (int i = st; i <= en; ++i) {
                id[l[i]] = id[r[i] + 1] = 1;
            }
            id[n + 1] = 1;
            vector <pair <int, int> > block_order;
            for (int i = 1; i <= n + 1; ++i) {
                id[i] += id[i-1];
                sum[id[i]] += a[i];
                if (id[i] != id[i-1]) {
                    sort(block_order.begin(), block_order.end());
                    for (int j = 0; j < block_order.size(); ++j)
                        order[block_order[j].second] = j + 1;
                    block_order.clear();

                    block_start[id[i]] = i;
                    _min[id[i]] = _max[id[i]] = a[i], cnt_min[id[i]] = cnt_max[id[i]] = 1;
                }
                else change(a[i], id[i]);

                if (i <= n) block_order.push_back(make_pair(a[i], i));
            }
            for (int i = 1; i <= id[n]; ++i) sz[i] = block_start[i+1] - block_start[i];

            for (int i = st; i <= en; ++i) {
                int lid = id[l[i]], rid = id[r[i]];
                if (type[i] == 1) {
                    for (int j = lid; j <= rid; ++j) {
                        if (_max[j] - _min[j] > 1) {
                            _max[j] = -inf, _min[j] = inf, sum[j] = 0;
                            for (int k = block_start[j]; k < block_start[j+1]; ++k) {
                                a[k] = sqrt(a[k] + offset[j]);
                                change(a[k], j);
                                sum[j] += a[k];
                            }
                        }
                        else {
                            _min[j] = sqrt(_min[j] + offset[j]);
                            _max[j] = sqrt(_max[j] + offset[j]);
                            if (_max[j] == _min[j]) cnt_min[j] = cnt_max[j] = sz[j];
                        }
                        offset[j] = 0;
                    }
                }
                else if (type[i] == 2) {
                    long long ans = 0;
                    for (int j = lid; j <= rid; ++j) ans += get_sum(j);
                    cout << ans << '\n';
                }
                else {
                    for (int j = lid; j <= rid; ++j) offset[j] += x[i];
                }
            }

            for (int i = 1; i <= n; ++i) {
                int j = id[i];
                if (_max[j] - _min[j] > 1) a[i] += offset[j];
                else if (_max[j] - _min[j] == 1) {
                    if (order[i] <= cnt_min[j]) a[i] = _min[j] + offset[j];
                    else a[i] = _max[j] + offset[j];
                }
                else a[i] = _min[j] + offset[j];
            }
        }
    }
    return 0;
}