LOJ 10128 花神游历各国
线段树维护\(\max\), \(sum\) 因为每个数最多被开根\(\log \log a-i\)次，所以直接暴力修改。
当某个区间所有数开根后值不变时不用再修改，即\(0\leq a-i\leq 1\)。
时间复杂度\(\mathjaxcal{O}(m\log n+n\log \log
a)\)
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#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
#define lson (p << 1)
#define rson (p << 1 | 1)
#define mid ((l + r) >> 1)
ll sum[N << 2];
int mx[N << 2], a[N], n, m;
void pushup(int p) {
sum[p] = sum[lson] + sum[rson];
mx[p] = max(mx[lson], mx[rson]);
}
void build(int p, int l, int r) {
if (l == r) {
sum[p] = (ll)a[l];
mx[p] = a[l];
return;
}
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(p);
}
void modify(int p, int l, int r, int L, int R) {
if (mx[p] <= 1) return;
if (l == r) {
a[l] = (int)sqrt(a[l]);
sum[p] = (ll)a[l];
mx[p] = a[l];
return;
}
if (L <= mid) modify(lson, l, mid, L, R);
if (R > mid) modify(rson, mid + 1, r, L, R);
pushup(p);
}
int qrymx(int p, int l, int r, int L, int R) {
if (l > R || r < L) return -1;
if (l >= L && r <= R) return mx[p];
return max(qrymx(lson, l, mid, L, R), qrymx(rson, mid + 1, r, L, R));
}
ll qrysum(int p, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (l >= L && r <= R) return sum[p];
return qrysum(lson, l, mid, L, R) + qrysum(rson, mid + 1, r, L, R);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
scanf("%d", &m);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int op, l, r;
scanf("%d %d %d", &op, &l, &r);
if (op == 1) printf("%lld\n", qrysum(1, 1, n, l, r));
else {
if (qrymx(1, 1, n, l, r) <= 1) continue;
modify(1, 1, n, l, r);
}
}
return 0;
}