花神游历各国

洛谷-P4145-花神游历各国

分析

区间开平方（取下整）。

⌊√​10​12​​​​​⌋=10​6​​。

⌊√​10​6​​​​​⌋=10​3​​。

⌊√​10​3​​​​​⌋=31。

⌊√​31​​​⌋=5。

⌊√​5​​​⌋=2。

⌊√​2​​​⌋=1。

实现

#include <iostream>
#include <cmath>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 1000010;
struct node {
    int l, r;
    LL sum, max_val;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define max_val(x) t[x].max_val
};
int n, m;
LL a[N];
node t[N << 2];

void update (int rt) {
    sum(rt) = sum(ls) + sum(rs);
    max_val(rt) = max(max_val(ls), max_val(rs));
}
void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        sum(rt) = a[l];
        max_val(rt) = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(rt);
}
void modify (int rt, int l, int r) {
    if (l(rt) == r(rt)) {
        sum(rt) = sqrt(sum(rt));
        max_val(rt) = sqrt(max_val(rt));
        return;
    }
    int mid = l(rt) + r(rt) >> 1;
    if (l <= mid && max_val(ls) >= 2) // 剪枝
        modify(ls, l, r);
    if (r >= mid + 1 && max_val(rs) >= 2)
        modify(rs, l, r);
    update(rt);
}
LL query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return sum(rt);
    int mid = l(rt) + r(rt) >> 1;
    LL res = 0;
    if (l <= mid) res += query(ls, l, r);
    if (r >= mid + 1) res += query(rs, l, r);
    return res;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);
    scanf("%d", &m);

    build(1, 1, n);
    while (m --) {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        if (l > r) swap(l, r);
        if (opt == 0)
            modify(1, l, r);
        else
            printf("%lld\n", query(1, l, r));
    }
    return 0;
}