rt，TLE 40pts，/qd/qd/qd

用 set 维护当前序列中不为 $1$ 的下标，每个数操作 $\log$ 次就被删除，感觉是对的啊

#include <bits/stdc++.h>
#define int long long
#define Sit set<int>::iterator
using namespace std; const int N = 1e5 + 5; 
int n, m, a[N]; set<int> s; vector<int> tmp;
struct SegmentTree {
    #define ls(x) ((x) << 1)
    #define rs(x) (((x) << 1) | 1)
    int sum[N << 2];
    void pushup(int x) { sum[x] = sum[ls(x)] + sum[rs(x)]; }
    void build(int x, int l, int r) {
        if (l == r) return sum[x] = a[l], void(); 
        int mid = (l + r) >> 1; build(ls(x), l, mid); 
        build(rs(x), mid + 1, r); pushup(x);
    }
    void modify(int x, int l, int r, int k, int v) {
        if (l == r) return sum[x] = v, void(); 
        int mid = (l + r) >> 1;
        if (k <= mid) modify(ls(x), l, mid, k, v);
        else modify(rs(x), mid + 1, r, k, v); pushup(x);
    }
    int qsum(int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return sum[x]; int mid = (l + r) >> 1, ret = 0;
        if (ql <= mid) ret += qsum(ls(x), l, mid, ql, qr);
        if (qr > mid) ret += qsum(rs(x), mid + 1, r, ql, qr); return ret;
    }
} SGT;
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
}
template<class T> void write(T x)
    { if (x > 9) write(x / 10); putchar(x % 10 + 48); }
template<class T> void print(T x, char ed = '\n') 
    { if (x < 0) putchar('-'), x = -x; write(x), putchar(ed); }
signed main() {
    read(n); 
    for (int i = 1; i <= n; ++i) 
        { read(a[i]); if (a[i] > 1) s.insert(i); }
    SGT.build(1, 1, n); read(m);
    for (int i = 1, op, l, r; i <= m; ++i) {
        read(op), read(l), read(r); if (l > r) swap(l, r);
        if (op == 2) {
            Sit ql = s.lower_bound(l), qr = s.upper_bound(r);
            for (Sit it = ql; it != qr; ++it) {
                a[*it] = sqrt(a[*it]); SGT.modify(1, 1, n, *it, a[*it]);
                if (a[*it] <= 1) tmp.emplace_back(*it);
            }
            for (int it : tmp) s.erase(it);
        } else print(SGT.qsum(1, 1, n, l, r));
    }
    return 0;
}