「SPOJ 2713」GSS4 - Can you answer these queries IV

Description

给定 $n\ (n \leq 10^5)$ 个数，已知 $\sum\limits_{i=1}^{n}a_i \leq 10^{18}$。

$m\ (m \leq 10^5)$ 个操作（操作有 $2$ 种）：

0 x y：将区间 $[x,y]\ (1 \leq x,y \leq n)$ 内的每一个数开 平方根（下取整） 。

1 x y：询问区间 $[x,y]\ (1 \leq x,y \leq n)$ 所有数的和（不保证 $x \leq y$，若 $x > y$，则交换 $x,y$）。

Source

[Luogu]SP2713

[SPOJ]GSS4

Solution

前置知识：

线段树

因为要维护区间和，所以我们想到用线段树来维护。

但是会发现懒惰标记不能打，那该怎么办呢？

考虑暴力修改：

$a[i]$ 最大为 $10^{18}$。

$$\left \lfloor \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{10^{18}}}}}}}\right \rfloor = 1$$

换言之，

$$\left \lfloor \sqrt[2^6]{10^{18}}\right \rfloor = 1$$

一个数最多开 $6$ 次平方根就会变成 $1$ 。

因为 $\sqrt{1} = 1,\sqrt{0} = 0$，

我们只需要维护 区间和 与 区间最大值 即可，

当一个区间的最大值 $\leq 1$ 时，我们对这个区间的修改就是无用的，因为无论怎么修改这个数仍是它本身。

而我们对一个数的开平方操作不会超过 $6$ 次，所以时间复杂度仍是 $O(n \log n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5 + 10;

struct SegmentTree {
    LL sum[MAXN << 2], maxx[MAXN << 2];

    inline int lson(int x) {
        return x << 1;
    }
    inline int rson(int x) {
        return x << 1 | 1;
    }
    inline void pushUp(int x) {
        sum[x] = sum[lson(x)] + sum[rson(x)];
        maxx[x] = max(maxx[lson(x)], maxx[rson(x)]);
    }
    void build(int x, int l, int r, LL *a) {
        if (l == r) {
            sum[x] = a[l];
            maxx[x] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson(x), l, mid, a), build(rson(x), mid + 1, r, a);
        pushUp(x);
    }
    void update(int ql, int qr, int l, int r, int x) {
        if (maxx[x] <= 1) return;//如果区间最大值小于等于1，就可以直接忽略这个区间的修改操作
        if (l == r) {
            sum[x] = sqrt(sum[x]);
            maxx[x] = sqrt(maxx[x]);
            return;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid) update(ql, qr, l, mid, lson(x));
        if (qr > mid) update(ql, qr, mid + 1, r, rson(x));
        pushUp(x);
    }
    LL query(int ql, int qr, int l, int r, int x) {
        if (ql <= l && qr >= r) return sum[x];
        int mid = (l + r) >> 1;
        LL res = 0;
        if (ql <= mid) res += query(ql, qr, l, mid, lson(x));
        if (qr > mid) res += query(ql, qr, mid + 1, r, rson(x));
        return res;
    }
} tr;

int n, m;
LL a[MAXN];

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    tr.build(1, 1, n, a);
    read(m);
    for (int opt, l, r, i = 1; i <= m; ++i) {
        read(opt), read(l), read(r);
        if (l > r) swap(l, r);
        if (opt == 1) {
            write(tr.query(l, r, 1, n, 1));
            putchar('\n');
        } else tr.update(l, r, 1, n, 1);
    }
    return 0;
}