题目地址：洛谷：【P4145】上帝造题的七分钟2 / 花神游历各国 – 洛谷、BZOJ：Problem 3038. — 上帝造题的七分钟2

题目描述

XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
“第一分钟，X说，要有数列，于是便给定了一个正整数数列。
第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。

题意简述

给你一个序列，两种操作：

1. 区间每个数开方
2. 区间求和

输入输出格式

输入格式：
第一行一个整数n，代表数列中数的个数。
第二行n个正整数，表示初始状态下数列中的数。
第三行一个整数m，表示有m次操作。
接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。

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

输入输出样例

输入样例#1：

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：

19
7
6

说明

1：对于100%的数据，1<=n<=100000，1<=l<=r<=n，数列中的数大于0，且不超过1e12。
2：数据不保证L<=R 若L>R，请自行交换L,R，谢谢！

题解

考虑线段树做，但是发现开放操作没法打标记，因此只能一路递归到底。
然而这样会TLE，因此我们要优化。我们发现每次开方都会对指数数量级减半，没几次开方数就会变为1，1开方仍是1，因此对于那些区间内不含大于1的区间，我们没必要继续递归对它们开方了，节省了不少的时间。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

int n, m;

LL a[MAXN], sum[MAXN << 2], mx[MAXN << 2];

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

inline void build(int o, int l, int r) {
    if(l == r) {
        mx[o] = sum[o] = a[l]; return;
    }
    build(lch, l, mid);
    build(rch, mid + 1, r);
    sum[o] = sum[lch] + sum[rch];
    mx[o] = std::max(mx[lch], mx[rch]);
}

inline void modify(int o, int l, int r, int ll, int rr) {
    if(l == r) {
        mx[o] = sum[o] = sqrt(sum[o]); return;
    }
    if(ll <= mid && mx[lch] > 1) modify(lch, l, mid, ll, rr);
    if(rr > mid && mx[rch] > 1) modify(rch, mid + 1, r, ll, rr);
    sum[o] = sum[lch] + sum[rch];
    mx[o] = std::max(mx[lch], mx[rch]);
}

inline LL query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) return sum[o];
    LL res = 0;
    if(ll <= mid) res += query(lch, l, mid, ll, rr);
    if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
    return res;
}

int op, l, r;

int main() {
    n = readint(); 
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    build(1, 1, n);
    m = readint();
    while(m--) {
        op = readint(); l = readint(); r = readint();
        if(l > r) std::swap(l, r);
        if(op == 0) {
            modify(1, 1, n, l, r);
        } else {
            printf("%lld\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}