数列分块入门 5

LibreOJ-6281-数列分块入门 5

分析

• 区间开方
• 区间求和

实现

#include <iostream>
#include <cmath>
using namespace std;

const int N = 50010, T = 230;
int n, a[N];
int pos[N], L[T], R[T];
int sum[T];
bool mark[T];

void initialize () {
    int t = sqrt(n);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
    }
    if (R[t] < n) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }

    for (int i = 1; i <= t; ++ i) {
        for (int j = L[i]; j <= R[i]; ++ j) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
}
void solve (int k) {
    if (mark[k] == true) return;

    mark[k] = true;
    sum[k] = 0;
    for (int i = L[k]; i <= R[k]; ++ i) {
        a[i] = sqrt(a[i]);
        sum[k] += a[i];
        if (a[i] >= 2) mark[k] = false;
    }
}
void modify (int l, int r) {
    int x = pos[l], y = pos[r];
    if (x == y) {
        for (int i = l; i <= r; ++ i) {
            sum[x] -= a[i];
            a[i] = sqrt(a[i]);
            sum[x] += a[i];
        }
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) solve(i);
        for (int i = l; i <= R[x]; ++ i) {
            sum[x] -= a[i];
            a[i] = sqrt(a[i]);
            sum[x] += a[i];
        }
        for (int i = L[y]; i <= r; ++ i) {
            sum[y] -= a[i];
            a[i] = sqrt(a[i]);
            sum[y] += a[i];
        }
    }
}
int query (int l, int r) {
    int x = pos[l], y = pos[r];
    int res = 0;
    if (x == y) {
        for (int i = l; i <= r; ++ i) res += a[i];
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) res += sum[i];
        for (int i = l; i <= R[x]; ++ i) res += a[i];
        for (int i = L[y]; i <= r; ++ i) res += a[i];
    }
    return res;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    initialize();
    for (int i = 1, opt, l, r, c; i <= n; ++ i) {
        cin >> opt >> l >> r >> c;
        if (opt == 0) {
            modify(l, r);
        } else {
            cout << query(l, r) << endl;
        }
    }
    return 0;
}