BZOJ3211 - 花神游历各国

已知每个数最多能被开方而减小的次数是有限的,当当前的数是 $0$ 或 $1$ 时就没有必要操作。

所以我们可以用线段树维护区间最大值,如果当前的最大值已经等于 $0$ 或 $1$ ,就无需操作,否则逐个修改。

复杂度 $O(n \sqrt {10^9} \log n)$ ,可过。

区间取模操作同理。

理论上来说资瓷区间开方 / 取模和单点修改,算是优美的暴力吧。


多倍经验(数据范围和要求略有不同):

  1. BZOJ3211 - 花神游历各国
  2. 洛谷4145 - 上帝造题的七分钟2 / 花神游历各国
  3. SPOJ2713 - GSS4 - Can you answer these queries IV

代码:

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll read() {
ll x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010;
int n, m, l, r, opt;
ll a[maxn];

struct node {
int l, r, mid;
ll sum, max;
} p[maxn << 2];

void build(int l, int r, int u = 1) {
p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
if (l == r) {
if (a[l] == 0) {
p[u].max = 1, p[u].sum = 0;
} else p[u].max = p[u].sum = a[l];
return;
}
build(l, p[u].mid, u << 1);
build(p[u].mid + 1, r, u << 1 | 1);
p[u].sum = p[u << 1].sum + p[u << 1 | 1].sum;
p[u].max = max(p[u << 1].max, p[u << 1 | 1].max);
}

void modify(int l, int r, int u = 1) {
if (p[u].max == 1) {
return;
}
if (p[u].l == p[u].r) {
p[u].sum = p[u].max = sqrt(p[u].sum);
return;
}
if (r <= p[u].mid) modify(l, r, u << 1);
else if (l > p[u].mid) modify(l, r, u << 1 | 1);
else modify(l, p[u].mid, u << 1), modify(p[u].mid + 1, r, u << 1 | 1);
p[u].sum = p[u << 1].sum + p[u << 1 | 1].sum;
p[u].max = max(p[u << 1].max, p[u << 1 | 1].max);
}

ll query(int l, int r, int u = 1) {
if (p[u].l == l && p[u].r == r) {
return p[u].sum;
}
if (r <= p[u].mid) return query(l, r, u << 1);
else if (l > p[u].mid) return query(l, r, u << 1 | 1);
else return query(l, p[u].mid, u << 1) + query(p[u].mid + 1, r, u << 1 | 1);
}

int main() {

n = read();
for (int i = 1; i <= n; i++)
a[i] = read();

build(1, n);

m = read();
for (int i = 1; i <= m; i++) {
opt = read(), l = read(), r = read();
if (l > r) swap(l, r);
if (opt == 2) {
modify(l, r);
} else {
printf("%lld\n", query(l, r));
}
}

return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×