给定长为 $n$ 的数列,$m$ 次操作涉及区间开方下取整、区间求和。
$n \leq 10^5, m \leq 2 \times 10^5, 1 \leq a_i \leq 10^9$。
BZOJ 3211

题解

分块和线段树都难以对区间开方,故考虑暴力开方。
注意到数列中最大可能的值 $10^9$ 只需开方 $5$ 次即变成 $1$,因此任何区间最多需要暴力开方 $5$ 次,之后开方操作不会影响此区间,可维护其区间和。更新时标记这样的区间,查询时可以直接加上这些区间,其他区间暴力求和即可。使用分块和线段树都容易实现。
(然而我写分块后被卡掉了,常数优化并没有什么用)

代码

线段树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cmath>
#define LC(x) ((x) << 1)
#define RC(x) (((x) << 1) | 1)
#define MID(x, y) (((x) + (y)) >> 1)
const int MAXN = 100005;
namespace S {
int n, a[MAXN];
struct Seg {
int l, r;
long long sum;
bool done, tag;
} segs[MAXN << 2];
inline void init(int x, int l, int r) {
Seg &seg = segs[x];
seg.l = l;
seg.r = r;
if (l == r) {
seg.sum = a[l];
} else {
int mid = MID(l, r);
init(LC(x), l, mid);
init(RC(x), mid + 1, r);
seg.sum = segs[LC(x)].sum + segs[RC(x)].sum;
}
seg.done = seg.sum <= 1;
}
inline void update(int x, int l, int r) {
Seg &seg = segs[x];
if (seg.done || seg.l > r || seg.r < l)
return;
if (l <= seg.l && seg.r <= r && seg.l == seg.r) {
seg.sum = sqrt(seg.sum);
if (seg.sum <= 1)
seg.done = true;
return;
}
update(LC(x), l, r);
update(RC(x), l, r);
seg.sum = segs[LC(x)].sum + segs[RC(x)].sum;
if (segs[LC(x)].done && segs[RC(x)].done)
seg.done = true;
}
inline long long query(int x, int l, int r) {
Seg &seg = segs[x];
if (seg.l > r || seg.r < l)
return 0;
if (l <= seg.l && seg.r <= r)
return seg.sum;
return query(LC(x), l, r) + query(RC(x), l, r);
}
}
int main() {
int m, opt, x, y, i;
scanf("%d", &S::n);
for (i = 1; i <= S::n; ++i)
scanf("%d", &S::a[i]);
S::init(1, 1, S::n);
scanf("%d", &m);
for (i = 0; i < m; ++i) {
scanf("%d%d%d", &opt, &x, &y);
if (opt == 1)
printf("%lld\n", S::query(1, x, y));
else
S::update(1, x, y);
}
return 0;
}

分块(TLE):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <cstdio>
#include <cmath>
const int MAXN = 100005;
const int MAXB = 1000;
namespace S {
int n, bsize, a[MAXN];
struct Block {
long long old_sum;
int done;
};
static Block blocks[MAXB];
inline int bmap(int x) {
return (x - 1) / bsize + 1;
}
inline int bl(int x) {
return (x - 1) * bsize + 1;
}
inline int br(int x) {
return x * bsize;
}
inline void init() {
bsize = ceil(sqrt(n));
for (int i = 1; i <= n; ++i)
blocks[bmap(i)].old_sum += a[i];
}
inline void update(int x, int y) {
int bx = bmap(x), by = bmap(y), i, old;
if (bx == by) {
for (i = x; i <= y; ++i) {
old = a[i];
a[i] = sqrt(a[i]);
blocks[bx].old_sum += a[i] - old;
}
} else {
bool done;
int r = br(bx), j;
for (i = x; i <= r; ++i) {
old = a[i];
a[i] = sqrt(a[i]);
blocks[bx].old_sum += a[i] - old;
}
for (i = bl(by); i <= y; ++i) {
old = a[i];
a[i] = sqrt(a[i]);
blocks[by].old_sum += a[i] - old;
}
for (i = bx + 1; i < by; ++i) {
Block &b = blocks[i];
if (b.done < bsize) {
done = true;
r = br(i);
for (j = bl(i) + b.done; j <= r; ++j) { // ***
if (a[j] > 1) {
old = a[j];
a[j] = sqrt(a[j]);
b.old_sum += a[j] - old;
if (done && a[j] > 1)
done = false, b.done = j - bl(i);
}
}
if (done)
b.done = bsize;
}
}
}
}
inline long long query(int x, int y) {
int bx = bmap(x), by = bmap(y), i;
long long res = 0;
if (bx == by) {
for (i = x; i <= y; ++i)
res += a[i];
} else {
int r = br(bx);
for (i = x; i <= r; ++i)
res += a[i];
for (i = bl(by); i <= y; ++i)
res += a[i];
for (i = bx + 1; i < by; ++i) {
res += blocks[i].old_sum;
}
}
return res;
}
}
int main() {
int m, opt, x, y, i;
scanf("%d", &S::n);
for (i = 1; i <= S::n; ++i)
scanf("%d", &S::a[i]);
S::init();
scanf("%d", &m);
for (i = 0; i < m; ++i) {
scanf("%d%d%d", &opt, &x, &y);
if (opt == 1)
printf("%lld\n", S::query(x, y));
else
S::update(x, y);
}
return 0;
}