[LOJ6281] 数列分块入门 5 - 分块

给定一个长为 \(n\) 的序列 \(a_1,...,a_n\)，有 \(n\) 个操作，包括区间开方下取整，区间求和

Solution

考虑到一个数开方 \(\log\) 次后就会变成 \(1\)，所以我们对每个区间记录一个值 mx

如果一个区间的 mx 不大于 \(1\)，那么显然我们的区间开方操作就无需执行

否则，我们暴力对这个区间内的所有元素进行开方

由于每个区间最多会被暴力开方 \(\log V\) 次，每个元素在区间开方时被暴力计算的次数不超过 \(O(n \log V)\)

总体时间复杂度 \(O(n(\sqrt n + \log V))\)

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

#define int long long
const int N = 200005;

int n, len, mx[N], a[N], b[N], s[N];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    len = ceil(sqrt(n));
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) b[i] = (i - 1) / len + 1;
    for (int i = 1; i <= n; i++) s[b[i]] += a[i], mx[b[i]] = max(mx[b[i]], a[i]);
    for (int i = 1; i <= n; i++) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if (!opt) {
            if (b[l] == b[r]) {
                for (int i = l; i <= r; i++) a[i] = sqrt(a[i]);
                mx[b[l]] = 0;
                s[b[l]] = 0;
                for (int i = b[l] * len - len + 1; i <= b[l] * len; i++)
                    mx[b[i]] = max(mx[b[i]], a[i]), s[b[i]] += a[i];
            } else {
                for (int i = b[l] + 1; i < b[r]; i++) {
                    if (mx[i] > 1) {
                        mx[i] = 0;
                        s[i] = 0;
                        for (int j = i * len - len + 1; j <= i * len; j++)
                            a[j] = sqrt(a[j]), mx[i] = max(mx[i], a[j]), s[i] += a[j];
                    }
                }
                for (int i = l; i <= b[l] * len; i++) a[i] = sqrt(a[i]);
                mx[b[l]] = 0;
                s[b[l]] = 0;
                for (int i = b[l] * len - len + 1; i <= b[l] * len; i++)
                    mx[b[i]] = max(mx[b[i]], a[i]), s[b[i]] += a[i];
                for (int i = b[r] * len - len + 1; i <= r; i++) a[i] = sqrt(a[i]);
                mx[b[r]] = 0;
                s[b[r]] = 0;
                for (int i = b[r] * len - len + 1; i <= b[r] * len; i++)
                    mx[b[i]] = max(mx[b[i]], a[i]), s[b[i]] += a[i];
            }
        } else {
            int ans = 0;
            if (b[l] == b[r]) {
                for (int i = l; i <= r; i++) ans += a[i];
            } else {
                for (int i = b[l] + 1; i < b[r]; i++) ans += s[i];
                for (int i = l; i <= b[l] * len; i++) ans += a[i];
                for (int i = b[r] * len - len + 1; i <= r; i++) ans += a[i];
            }
            cout << ans << endl;
        }
    }
}

[LOJ6281] 数列分块入门 5 - 分块

原文：https://www.cnblogs.com/mollnn/p/12702922.html