「BZOJ 3038」上帝造题的七分钟2

Description

给定 $n\ (n \leq 10^5)$ 个数,已知 $\sum\limits_{i=1}^{n}a_i \leq 10^{18}$。

$m\ (m \leq 10^5)$ 个操作(操作有 $2$ 种):

1 x y:询问区间 $[x,y]\ (1 \leq x,y \leq n)$ 所有数的和(不保证 $x \leq y$,若 $x > y$,则交换 $x,y$)。

2 x y:将区间 $[x,y]\ (1 \leq x,y \leq n)$ 内的每一个数开 平方根(下取整)

Source

[BZOJ]3038

Solution

前置知识:

线段树

因为要维护区间和,所以我们想到用线段树来维护。

但是会发现懒惰标记不能打,那该怎么办呢?

考虑暴力修改:

$a[i]$ 最大为 $10^{18}$。

换言之,

一个数最多开 $6$ 次平方根就会变成 $1$ 。

因为 $\sqrt{1} = 1,\sqrt{0} = 0$,

我们只需要维护 区间和区间最大值 即可,

当一个区间的最大值 $\leq 1$ 时,我们对这个区间的修改就是无用的,因为无论怎么修改这个数仍是它本身。

而我们对一个数的开平方操作不会超过 $6$ 次,所以时间复杂度仍是 $O(n \log n)$ 。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5 + 10;

struct SegmentTree {
LL sum[MAXN << 2], maxx[MAXN << 2];

inline int lson(int x) {
return x << 1;
}
inline int rson(int x) {
return x << 1 | 1;
}
inline void pushUp(int x) {
sum[x] = sum[lson(x)] + sum[rson(x)];
maxx[x] = max(maxx[lson(x)], maxx[rson(x)]);
}
void build(int x, int l, int r, LL *a) {
if (l == r) {
sum[x] = a[l];
maxx[x] = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson(x), l, mid, a), build(rson(x), mid + 1, r, a);
pushUp(x);
}
void update(int ql, int qr, int l, int r, int x) {
if (maxx[x] <= 1) return;//如果区间最大值小于等于1,就可以直接忽略这个区间的修改操作
if (l == r) {
sum[x] = sqrt(sum[x]);
maxx[x] = sqrt(maxx[x]);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) update(ql, qr, l, mid, lson(x));
if (qr > mid) update(ql, qr, mid + 1, r, rson(x));
pushUp(x);
}
LL query(int ql, int qr, int l, int r, int x) {
if (ql <= l && qr >= r) return sum[x];
int mid = (l + r) >> 1;
LL res = 0;
if (ql <= mid) res += query(ql, qr, l, mid, lson(x));
if (qr > mid) res += query(ql, qr, mid + 1, r, rson(x));
return res;
}
} tr;

int n, m;
LL a[MAXN];

int main() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
tr.build(1, 1, n, a);
read(m);
for (int opt, l, r, i = 1; i <= m; ++i) {
read(opt), read(l), read(r);
if (l > r) swap(l, r);
if (opt == 1) {
write(tr.query(l, r, 1, n, 1));
putchar('\n');
} else tr.update(l, r, 1, n, 1);
}
return 0;
}

本文标题:「BZOJ 3038」上帝造题的七分钟2

文章作者:Heartlessly

发布时间:2019年03月13日 - 15:21:45

最后更新:2019年05月28日 - 09:56:16

原始链接:https://heartlessly.github.io/problems/bzoj-3038/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%