题面

大秦为你打开题目传送门

题目背景

XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。

题目描述

“第一分钟，X 说，要有数列，于是便给定了一个正整数数列。

第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $64$ 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入格式

第一行一个整数 $n$，代表数列中数的个数。

第二行 $n$ 个正整数，表示初始状态下数列中的数。

第三行一个整数 $m$，表示有 $m$ 次操作。

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

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

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

数据中有可能 $l>r$，所以遇到这种情况请交换 $l$ 和 $r$。

输出格式

对于询问操作，每行输出一个回答。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
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

样例输出 #1

1
2
3
19
7
6

提示

对于 $30\%$ 的数据，$1\le n,m\le 10^3$，数列中的数不超过 $32767$。

对于 $100\%$ 的数据，$1\le n,m\le 10^5$，$1\le l,r\le n$，数列中的数大于 $0$，且不超过 $10^{12}$。

思路

开根号操作看似玄学，但是注意数据范围：$10^{12}$ ，这够我们开几次根号？不过区区 $6$ 次就会变成 $1$ 。 $1$ 开根号是什么？还是 $1$ 。这告诉我们什么？大力开根号，如果区间全是 $1$ 就不要继续了，不过区区带一个 $6$ 的常数，我们受得起。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// #pragma GCC optimize(2)
// #pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;

struct Node {
    int L, R;
    ll num;
    Node() {}
    Node(int L, int R, ll num) : L(L), R(R), num(num) {}
    Node operator + (const Node & b) const {
        return Node(min(L, b.L), max(R, b.R), num + b.num);
    }
};
class SegTree {
    private : 
        Node node[N << 2];
    public : 
        void Build(int p, int L, int R, ll *a) {
            // cout << L << ' ' << R << endl;
            node[p].L = L, node[p].R = R;
            if(L == R) {
                node[p].num = a[L];
                return ;
            }
            int mid = L + R >> 1;
            Build(p << 1, L, mid, a);
            Build(p << 1 | 1, mid + 1, R, a);
            node[p] = node[p << 1] + node[p << 1 | 1]; 
        }
        void Modify(int p, int L, int R) {
            if(L <= node[p].L && node[p].R <= R) {
                if(node[p].num == node[p].R - node[p].L + 1) {
                    return ;
                }
                if(node[p].L == node[p].R) {
                    node[p].num = sqrt(node[p].num);
                    return ;
                }
            }
            int mid = node[p].L + node[p].R >> 1;
            if(L <= mid) Modify(p << 1, L, R);
            if(mid < R) Modify(p << 1 | 1, L, R);
            node[p] = node[p << 1] + node[p << 1 | 1];
        }
        ll Query(int p, int L, int R) {
            if(L <= node[p].L && node[p].R <= R) {
                return node[p].num;
            }
            int mid = node[p].L + node[p].R >> 1;
            ll ans = 0;
            if(L <= mid) ans += Query(p << 1, L, R);
            if(mid < R) ans += Query(p << 1 | 1, L, R);
            return ans;
        }
};

int n, Q;
ll a[N];

SegTree tree;

inline void Input() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    read(Q);
}

inline void Work() {
    tree.Build(1, 1, n, a);
    // cout << 1 << endl;
    int op, x, y;
    while(Q--) {
        read(op, x, y);
        if(x > y) swap(x, y);
        if(op == 0) {
            tree.Modify(1, x, y);
        }
        else {
            printf("%lld\n", tree.Query(1, x, y));
        }
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}