题解：P13980 数列分块入门 5

· · 题解

思路分析

我们可以老老实实的分块，然后发现又是特殊性质修改类分块。

为什么说是特殊性质修改类呢？因为显然在这道题的数据范围下，一个数是开不了几次根的。

一个较为精确的上界是 \log\log n，因为每一次开根都是在指数上 \div2。

于是我们可以考虑分块。边角料直接处理，整块判断一下，如果有 >1 的元素就整块暴力更新，否则不更新。

总的时间复杂度上界为 O(n\sqrt n\log\log V)。代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define sipt
//#define sopt
struct IO {
#define mxsz (1 << 20)
    char buf[mxsz], * p1, * p2;
    char pbuf[mxsz], * pp;
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
    inline char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, mxsz, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
#ifndef sipt
    inline int read() {
        int r = 0; char c = gc(); while (c < '0' || c>'9') c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return r;
    }
#else
    inline int read() {
        int r = 0; char c = gc(); bool rev = 0;
        while (c < '0' || c>'9') rev |= (c == '-'), c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return rev ? ~r + 1 : r;
    }
#endif
    inline void push(const char& c) {
        if (pp - pbuf == mxsz) fwrite(pbuf, 1, mxsz, stdout), pp = pbuf;
        *pp++ = c;
    }
    inline void write(int x) {
        static char sta[22]; int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) push(sta[--top] ^ 48);
    }
    inline void write(int x, char opc) {
#ifdef sopt
        if (x < 0) push('-'), x = ~x + 1;
#endif
        write(x), push(opc);
    }
} io;
int n, a[300005], sz, sm[300005]; bool alz[300005];
#define blk(i) (i / sz)
inline bool chk(int bl) {
    for (int i = bl * sz; i != (bl + 1) * sz && i != n; ++i)
        if (a[i] > 1) return 1;
    return 0;
}
inline void chg(int l, int r) {
    int bl = blk(l), br = blk(r);
    if (bl == br) {
        if (!alz[bl])return;
        for (int i = l; i <= r; ++i)
            sm[bl] -= a[i],
            a[i] = sqrt(a[i]),
            sm[bl] += a[i];
        alz[bl] = chk(bl);
        return;
    }
    if (alz[bl]) {
        for (int i = l; i != sz * (bl + 1); ++i)
            sm[bl] -= a[i],
            a[i] = sqrt(a[i]),
            sm[bl] += a[i];
        alz[bl] = chk(bl);
    }
    if (alz[br]) {
        for (int i = br * sz; i <= r; ++i)
            sm[br] -= a[i],
            a[i] = sqrt(a[i]),
            sm[br] += a[i];
        alz[br] = chk(br);
    }
    for (int j = bl + 1; j != br; ++j) {
        if (alz[j]) {
            for (int i = j * sz; i != (j + 1) * sz; ++i)
                sm[j] -= a[i],
                a[i] = sqrt(a[i]),
                sm[j] += a[i];
            alz[j] = chk(j);
        }
    }
}
inline int que(int l, int r) {
    int bl = blk(l), br = blk(r), ret = 0;
    if (bl == br) {
        for (int i = l; i <= r; ++i) ret += a[i];
        return ret;
    }
    for (int i = l; i != sz * (bl + 1); ++i) ret += a[i];
    for (int i = br * sz; i <= r; ++i) ret += a[i];
    for (int j = bl + 1; j != br; ++j) ret += sm[j];
    return ret;
}
signed main() {
    ios::sync_with_stdio(0);
    sz = sqrt(n = io.read());
    for (int i = 0; i != n; ++i)
        sm[blk(i)] += (a[i] = io.read()),
        alz[blk(i)] |= (a[i] > 1);
    for (int i = 1, o, l, r, v; i <= n; ++i) {
        if (o = io.read(), l = io.read() - 1, r = io.read() - 1, o)
            io.write(que(l, r), '\n');
        else chg(l, r);
    }
}