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

题目描述

题意简述

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

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

输入输出格式

输入格式：

输出格式：
每次x=1时，每行一个整数，表示这次旅行的开心度

输入输出样例

输入样例#1：

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

输出样例#1：

101
11
11

说明

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

题解

和[BZOJ3038]上帝造题的七分钟2是一个题。

代码

// 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(op == 2) {
            modify(1, 1, n, l, r);
        } else {
            printf("%lld\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}