UOJ228. 基础数据结构练习题

博主： tony102
发布时间：2020 年 12 月 31 日
2163 次浏览
暂无评论
894字数
分类：题解

[Link](https://uoj.ac/problem/228)

## Sol

先考虑没有区间加操作怎么做。就直接暴力开根

现在有了区间加怎么做。题目里面的开根号是向下取整的。注意到数字多次开根以后都会变成一个定值。比如说：

` 5 8 9 4` 第一次开根以后变成 `2 2 3 2` ，再开一次就变成了 `1 1 1 1`

很好，很有精神！我们就来分一下这个性质。假设数是$v$， 那么经过$log_{log_v}$次开根就变成了定值。

有了这个性质，我们来考虑一下这个东西怎么维护。因为在$log_{log_v}$次开根后变成了定值，相当于我们的操作变成了区间赋值。什么时候赋值？最快到定值的是这个区间中$min$值，最后到达(可能与$min$值同时)的是区间$max$值。那么我们现在关心的就是区间中的最小最大值了。当我们进到一个区间进行更新的时候，假如最大最小值开根的值都一样了，说明我们可以区间赋值了。

分析一下复杂度，操作是 $O(log_{log_v})$ 的，平均深度$log_n$。那么渐进意义时间复杂度就是 $O(n log_nlog_{log_v})$

但是出现这样一种情况: `15 16 15 16 15 16 15 16` 这样交替相差$1$的情况。先开一次根，`3 4 3 4 3 4...` 开根以后仍然是交替相差$1$的。加入再加上$12$， 又变回了原来的情况。这种情况原来的复杂度就无法保证了。那么如何避免这种情况？当最小值和最大值只相差$1$的时候特判一下就可以了。

其他的标记下放等操作不变即可。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e5 + 5;

int n, q;
int a[SIZE];

struct node {
	int l, r, mi, mx, val, tag;
} tree[SIZE << 2];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

#define lson(p) p << 1
#define rson(p) p << 1 | 1

void update(int p, int x) {
	int len = tree[p].r - tree[p].l + 1;
	tree[p].val += x * len, tree[p].tag += x, tree[p].mi += x, tree[p].mx += x;
}

void pushDown(int p) {
	if (tree[p].tag) {
		update(lson(p), tree[p].tag); update(rson(p), tree[p].tag);
		tree[p].tag = 0;
	}
}

void pushUp(int p) {
	tree[p].mi = std::min(tree[lson(p)].mi, tree[rson(p)].mi);
	tree[p].mx = std::max(tree[lson(p)].mx, tree[rson(p)].mx);
	tree[p].val = tree[lson(p)].val + tree[rson(p)].val;
}

void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].val = tree[p].mi = tree[p].mx = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson(p), l, mid); build(rson(p), mid + 1, r);
	pushUp(p);
}

void modifySqrt(int p, int l, int r) {
	int tmp = 0;
	if (l <= tree[p].l && tree[p].r <= r && 
	   ((tree[p].mx == tree[p].mi) || (tree[p].mx == tree[p].mi + 1 && (tmp = sqrt(tree[p].mx)) * tmp == tree[p].mx))) {
			update(p, (tmp ? tmp : (int)(sqrt(tree[p].mx))) - tree[p].mx);
			return;
	}
	pushDown(p);
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) modifySqrt(lson(p), l, r);
	if (r > mid) modifySqrt(rson(p), l, r);
	pushUp(p);
}

void modifyAdd(int p, int l, int r, int v) {
	if (l <= tree[p].l && tree[p].r <= r) {
		int len = tree[p].r - tree[p].l + 1;
		tree[p].tag += v, tree[p].val += v * len, tree[p].mi += v, tree[p].mx += v;
		return;
	}
	pushDown(p);
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) modifyAdd(lson(p), l, r, v);
	if (r > mid) modifyAdd(rson(p), l, r, v);
	pushUp(p);
}

int query(int p, int l, int r) {
	if (l <= tree[p].l && tree[p].r <= r) return tree[p].val;
	pushDown(p);
	int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
	if (l <= mid) ans += query(lson(p), l, r);
	if (r > mid) ans += query(rson(p), l, r);
	return ans;
}

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read(), q = read();
	for (int i = 1; i <= n; ++ i) a[i] = read();
	build(1, 1, n);	
	int opt, l, r, x;
	while (q --) {
		opt = read(), l = read(), r = read();
		if (opt == 1) x = read(), modifyAdd(1, l, r, x);
		if (opt == 2) modifySqrt(1, l, r);
		if (opt == 3) printf("%lld\n", query(1, l, r));
	}
	return 0;
}
```

最后修改：2021 年 09 月 07 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

xbieygztgu
不错不错，我喜欢看 https://www.ea55.com/
ojvrnvtsvs
看的我热血沸腾啊https://www.ea55.com/
orzaztmfuh
不错不错，我喜欢看 https://www.ea55.com/
mzcwdjqqxe
不错不错，我喜欢看 https://www.ea55.com/
Yanws
牢师求更新

UOJ228. 基础数据结构练习题

tony102 • 2020 年 12 月 31 日

[Link](https://uoj.ac/problem/228)

## Sol

先考虑没有区间加操作怎么做。就直接暴力开根

现在有了区间加怎么做。题目里面的开根号是向下取整的。注意到数字多次开根以后都会变成一个定值。比如说：

` 5 8 9 4` 第一次开根以后变成 `2 2 3 2` ，再开一次就变成了 `1 1 1 1`

很好，很有精神！我们就来分一下这个性质。假设数是$v$， 那么经过$log_{log_v}$次开根就变成了定值。

分析一下复杂度，操作是 $O(log_{log_v})$ 的，平均深度$log_n$。那么渐进意义时间复杂度就是 $O(n log_nlog_{log_v})$

其他的标记下放等操作不变即可。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e5 + 5;

int n, q;
int a[SIZE];

struct node {
	int l, r, mi, mx, val, tag;
} tree[SIZE << 2];

#define lson(p) p << 1
#define rson(p) p << 1 | 1

void update(int p, int x) {
	int len = tree[p].r - tree[p].l + 1;
	tree[p].val += x * len, tree[p].tag += x, tree[p].mi += x, tree[p].mx += x;
}

void pushDown(int p) {
	if (tree[p].tag) {
		update(lson(p), tree[p].tag); update(rson(p), tree[p].tag);
		tree[p].tag = 0;
	}
}

void pushUp(int p) {
	tree[p].mi = std::min(tree[lson(p)].mi, tree[rson(p)].mi);
	tree[p].mx = std::max(tree[lson(p)].mx, tree[rson(p)].mx);
	tree[p].val = tree[lson(p)].val + tree[rson(p)].val;
}

UOJ228. 基础数据结构练习题

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

写在虎年末

Luogu3979 遥远的国度

关于一些题解和讲题

ARC124A LR Constraint

Luogu5513 [CEOI2013]Board

UOJ228. 基础数据结构练习题

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

UOJ228. 基础数据结构练习题

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款