這道題是受到大犇MagHSK的啟發我才得以想出來的，蒟蒻覺得自己的代碼跟MagHSK大犇的代碼完全比不上，所以這裡蒟蒻就套用了MagHSK大犇的代碼（大家可以關注下我的博客，友情鏈接就是大犇MagHSK的博客，大神是山東省隊隊員，他的博客中的題的質量都比我高幾個檔次）；
這是大神MagHSK的解釋：因為10^9頂多開5~6次方就成了1了（當然這裡的等於是向下取整的）因此對於修改操作，如果某一段不是1或不是0，就暴力修改，如果是1/0就不管他。修改完之後update一下就好了。
題目上說我們給出的是一個可修改（修改的規則就是對要修改的區間內每個數開平方）、可查詢（就是求一段區間上所有數字的和）的一個數列。
顯然我們直接暴力的效率是很低的，那麼我們就采取了線段樹——一種神奇的數據結構。
線段樹作為可修改可查詢的數據結構，基本操作就是點更新、區間更新和區間查詢（包括最小值、最大值和區間和）這裡因為是解題報告，所以就不跟大家講基本思路了，直接進入正題，基本思路和代碼板子請自己去看。
這裡因為是對區間內的數開平方，所以區間更新就有點不大好用了（主要是沒法直接標記區間然後開平方，這樣會計算錯誤），然後數據范圍也不算大，所以我們就考慮搜索線段樹上的每一個在需要update（更新）的區間的所有點進行開方點更新，然後再push_up（往上面推，求出每個線段樹上區間的和）上去。這樣就可以完成更新任務了。（push_up和change（update）函數代碼跟板子上不大一樣，all數組就是標記這個區間內的數還值不值得進行開平方操作，顯然如果這個區間內的和為1或者0的時候就不用開平方了，change的時候就可以省略了）。
區間查詢的操作就是套板子，這個沒什麼需要思考的。
還是那句老話，要先考慮自己寫，然後實在不會了再看題解，總是copy別人的代碼自己的水平肯定上升得很慢。
廢話不再說，上代碼。
1 #include <cstdio>
2 #include <algorithm>
3 #include <cmath>
4 using namespace std;
5 typedef long long LL;
6 const int INF = 1009999999;
7 int n;
8 LL sum[500005], A[500005];
9 bool all[500005];
10 void pu(int now) {
11 sum[now] = sum[now << 1] + sum[now << 1 | 1];
12 all[now] = all[now << 1] && all[now << 1 | 1];
13 }
14 void build(int now, int l, int r) {
15 if (l == r) {
16 sum[now] = A[l];
17 if (sum[now] == 1 || sum[now] == 0)
18 all[now] = true;
19 return;
20 }
21 int mid = (l + r) >> 1;
22 build(now << 1, l, mid);
23 build(now << 1 | 1, mid + 1, r);
24 pu(now);
25 }
26 LL query(int now, int l, int r, int ll, int rr) {
27 if (ll <= l && r <= rr) {
28 return sum[now];
29 }
30 int mid = (l + r) >> 1;
31 LL ret = 0;
32 if (ll <= mid) ret += query(now << 1, l, mid, ll, rr);
33 if (rr > mid) ret += query(now << 1 | 1, mid + 1, r, ll, rr);
34 return ret;
35 }
36 void change(int now, int l, int r, int ll, int rr) {
37 if (all[now]) {
38 return;
39 }
40 if (l == r) {
41 sum[now] = sqrt(sum[now]);
42 if (sum[now] == 1 || sum[now] == 0)
43 all[now] = true;
44 return;
45 }
46 int mid = (l + r) >> 1;
47 if (ll <= mid) change(now << 1, l, mid, ll, rr);
48 if (rr > mid) change(now << 1 | 1, mid + 1, r, ll, rr);
49 pu(now);
50 }
51 int main() {
52 scanf("%d", &n);
53 for (int i = 1; i <= n; ++i)
54 scanf("%lld", A+i);
55 build(1, 1, n);
56 int m, x, y, z;
57 scanf("%d", &m);
58 while (m--) {
59 scanf("%d%d%d", &x, &y, &z);
60 if (y > z) swap(y, z);
61 if (x==1) {
62 printf("%lld\n", query(1, 1, n, y, z));
63 } else {
64 change(1, 1, n, y, z);
65 }
66 }
67 return 0;
68 }
這次解題報告就完結啦，蒟蒻一般是在每周的星期三晚和星期天晚發解題報告，大家就不要在其他時間翻我的博客啦。
