题解：P13980 数列分块入门 5

xAlec · 2025-09-06 16:55:00 · 题解

Solution

区间开方区间和，如果你做过这道题那应该是比较熟悉的。

对于一个数 v，实际上开平方不用多少次就可以使它变成 1，这个级别大概是 O(\log\log v) 的。

记块长为 T。

这样一来我们考虑比较暴力的修改，对于散块每次 a_i \leftarrow \sqrt{a_i} 然后同步更新块内和 sum_{blk_i}，复杂度 O(T\log\log \left|V\right|)。

对于整块，如果说块内元素均小于等于 1，给该块打上标记下次就不处理了，复杂度 O(nT\log\log v)。

加上询问就是 O(nT\log\log v + n(\frac{n}{T} + T))，在 T = \sqrt{\frac{n}{\log\log \left|V\right|}} 时最快。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int res = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
    return res * f;
}
constexpr int MAXN = 3e5 + 10;
int n, A[MAXN], opt, l, r, c, blk[MAXN], Sum[MAXN], siz;
bool vis[MAXN];

inline void Modify (int ql, int qr) {
    int lpos = blk[ql], rpos = blk[qr];
    if (lpos == rpos) {
        for (int i = ql; i <= qr; i ++) {
            Sum[lpos] -= A[i];
            A[i] = sqrt(A[i]);
            Sum[lpos] += A[i];
        }
    } else {
        for (int i = ql; blk[i] == lpos; i ++) {
            Sum[lpos] -= A[i];
            A[i] = sqrt(A[i]);
            Sum[lpos] += A[i];
        }
        for (int i = qr; blk[i] == rpos; i --) {
            Sum[rpos] -= A[i];
            A[i] = sqrt(A[i]);
            Sum[rpos] += A[i];
        } 
        for (int i = lpos + 1; i <= rpos - 1; i ++) {
            if (vis[i]) continue;
            int l = (i - 1) * siz + 1, r = min (n, i * siz);
            bool flag = true;
            for (int j = l; j <= r; j ++) {
                Sum[i] -= A[j];
                A[j] = sqrt(A[j]);
                Sum[i] += A[j];
                flag = flag & !(A[j] && A[j] ^ 1);
            }
            if (flag) vis[i] = true;
        }
    }
}

inline int Query (int ql, int qr) {
    int lpos = blk[ql], rpos = blk[qr], tmpSum = 0;
    if (lpos == rpos) {
        for (int i = ql; i <= qr; i ++)
            tmpSum += A[i];
    } else {
        for (int i = ql; blk[i] == lpos; i ++)
            tmpSum += A[i];
        for (int i = qr; blk[i] == rpos; i --)
            tmpSum += A[i];
        for (int i = lpos + 1; i <= rpos - 1; i ++)
            tmpSum += Sum[i];
    }
    return tmpSum;
}

// function()

signed main() {
    n = read(), siz = sqrt(n);
    for (int i = 1; i <= n; i ++) {
        A[i] = read();
        blk[i] = (i - 1) / siz + 1;
        Sum[blk[i]] += A[i];
    }
    // readin()
    for (int i = 1; i <= n; i ++) {
        opt = read(), l = read(), r = read();
        if (!opt) {
            Modify (l, r);
        } else {
            printf ("%lld\n", Query (l, r));
        }
    }
    // output answer
    return 0;
}