大伙写的都是线段树,感觉还是补一个树状数组+并查集的解法好一些。
其他题解都写过了,每个不小于1的数至多被开根号5次之后就会变成1(0则一直是0),那么我们可以参照 AcWing 3115. 疯狂的馒头 一题,利用并查集来模拟区间染色的过程。
在这里,我们要做的就是当有数变得小于等于1之后,这个数就不再会被操作了,就该将其从可处理的区间中剔除掉。每次从左到右的过程跟区间染色完全一致,只是还可以操作的数我们不能无脑剔除。每次操作的时候都是单点操作,直接在树状数组上加一个“当前值开根-当前值”就行了。
struct union_find
{
int n;
vector<int> f;
union_find(int _n = 0) : n(_n) { f.resize(n + 2); }
int getf(int x)
{
assert(x <= (n + 1));
return f[x] ? (f[x] = getf(f[x])) : x;
}
void erase(int x) { f[x] = getf(x + 1); }
int nxt_lower(int x) { return getf(x); } // 寻找大于等于 x 的下一个可处理点 (确定区间起点用)
int nxt_upper(int x) { return getf(x + 1); } // 寻找大于 x 的下一个可处理点 (区间往后遍历用)
};
struct BIT
{
int N;
vector<i64>& a;
BIT(vector<i64>& _a) : a(_a), N(_a.size() - 1)
{
for (int i = 1; i <= N; ++i)
{
int f = i + (i & (-i));
if (f <= N)
a[f] += a[i];
}
}
void add(int k, i64 x)
{
for (; k <= N; k += (k & (-k)))
a[k] += x;
}
i64 sum(int k)
{
if (k <= 0)
return (i64)0;
i64 ret = 0;
for (; k; k -= (k & (-k)))
ret += a[k];
return ret;
}
i64 query(int l, int r) { return sum(r) - sum(l - 1); }
};
int main()
{
int n = rd();
vector<i64> a(n + 1), s(n + 1);
for (int i = 1; i <= n; ++i)
a[i] = s[i] = rd();
BIT bit = BIT(s);
union_find uf(n);
int m = rd();
while (m--)
{
int op = rd(), l = rd(), r = rd();
if (op == 1)
wr(bit.query(l, r)), putchar('\n');
else
{
int cur = uf.nxt_lower(l);
while (cur <= r)
{
i64 v = (i64)sqrtl(a[cur]);
bit.add(cur, v - a[cur]), a[cur] = v;
if (a[cur] <= 1)
uf.erase(cur);
cur = uf.nxt_upper(cur);
}
}
}
}