题解 P4145 【上帝造题的七分钟2 / 花神游历各国】

forlight · 2019-07-28 12:30:08 · 题解

n=10w,区间修改，区间求和，大家想到了什么？

没错，线段树！

不过，区间操作是开方，不满足结合律，只能每次以暴力的方式进行修改，复杂度受不了，怎么办？

大家知道，连续开方能使一个数迅速收敛，1e12左右的数在6-7次开方后就会变至1或0，而1或0的开方等于本身

那么，我们在线段树的每个区间维护一个信息：该区间内是否都是1或0，在修改时如果碰到这种区间就直接返回

大致思路就是这样

当然，这个题目也有一些小坑点：

1.<=1e12，意味着你必须开long long 2.l>r时，你必须手动换回来

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100010;
int n, m;
struct tree {
    LL sum;
    bool flag;
    int l, r;
} a[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
void pushup(int x) {
    a[x].sum = a[ls(x)].sum + a[rs(x)].sum;
    a[x].flag = (a[ls(x)].flag && a[rs(x)].flag);
}
void build(int x, int l, int r)
{
    a[x].l = l, a[x].r = r;
    if (l == r) {
        scanf("%lld", &a[x].sum);
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    pushup(x);
}
LL query(int x, int l, int r) {
    if (l <= a[x].l && a[x].r <= r)
        return a[x].sum;
    int mid = (a[x].l + a[x].r) >> 1;
    LL res = 0;
    if (l <= mid) res += query(ls(x), l, r);
    if (r >  mid) res += query(rs(x), l, r);
    return res;
}
void change(int x, int l, int r) {
    if (a[x].flag) return;
    if (a[x].l == a[x].r) {
        a[x].sum = sqrt(a[x].sum);
        a[x].flag = (a[x].sum == 0 || a[x].sum == 1);
        return;
    }
    int mid = (a[x].l + a[x].r) >> 1;
    if (l <= mid) change(ls(x), l, r);
    if (r >  mid) change(rs(x), l, r);
    pushup(x);
}
int main()
{
    int n, m;
    scanf("%d", &n);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        if (l > r) swap(l, r);
        if (opt) printf("%lld\n", query(1, l, r));
        else change(1, l, r);
    }
    return 0;
}