题解【luoguP4145 上帝造题的七分钟2（花神游历各国）】

题目链接

题解

题目大意：

一个序列，支持区间开方与求和操作。

算法：线段树实现开方修改与区间求和

分析：

显然，这道题的求和操作可以用线段树来维护
但是如何来实现区间开方呢
大家有没有这样的经历：玩计算器的时候，把一个数疯狂的按开方，最后总会变成 \(1\)，之后在怎样开方也是 \(1\) (\(\sqrt1=1\))
同样的，\(\sqrt0=0\)
所以，只要一段区间里的所有数全都 \(\leq 1\) 了，便可以不去修改它

实现：

线段树维护区间和 \(sum\) 与最大值 \(Max\)
在修改过程中，只去修改 \(Max > 1\) 的区间
到了叶子节点对\(sum\)和\(Max\)进行开方就行了

复杂度：

每个数 \(\leq 10 ^ {12}\),所以至多开方\(6\)次便可以得到\(1\)
每次操作是 \(\log n\)的，总复杂度\(O(n \log n)\)

注意事项：

请使用long long
可能 \(l > r\)(把我坑了)

代码:

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <cstdio>

using namespace std;

typedef long long LL;

const int MAXN = 100100;

int n, m;

int cnt;

LL a[MAXN];

struct node

{

	int left, right;

	LL s, Max;

	node *ch[2];

}pool[MAXN << 2], *root;

inline void pushup(node *r)

{

	r->s = r->ch[0]->s + r->ch[1]->s;

	r->Max = max(r->ch[0]->Max, r->ch[1]->Max);

}

inline void Build_Tree(node *r, int left, int right)

{

	r->left = left;

	r->right = right;

	if(left == right)

	{

		r->s = r->Max = a[left];

		return ;

	}

	int mid = (left + right) / 2;

	node *lson = &pool[++cnt];

	node *rson = &pool[++cnt];

	r->ch[0] = lson;

	r->ch[1] = rson;

	Build_Tree(lson, left, mid);

	Build_Tree(rson, mid + 1, right);

	pushup(r);

}

inline void change(node *r, int left, int right)

{

	if(r->left == r->right)

	{

		r->s = sqrt(r->s);

		r->Max = sqrt(r->Max);

		return ;

	}

	int mid = (r->left +r-> right) / 2;

	if(left <= mid && r->ch[0]->Max > 1) change(r->ch[0], left, right);

	if(mid < right && r->ch[1]->Max > 1) change(r->ch[1], left, right);

	pushup(r);

}

inline LL query(node *r, int left, int right)

{

	if(r->left == left && r->right == right)

		return r->s;

	if(r->ch[0]->right >= right) return query(r->ch[0], left, right);

	else if(r->ch[1]->left <= left) return query(r->ch[1], left, right);

	else

		return query(r->ch[0], left, r->ch[0]->right) +

		       query(r->ch[1], r->ch[1]->left, right);

}

int main()

{

    scanf("%d", &n);

    root = &pool[0];

    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    scanf("%d", &m);

    Build_Tree(root, 1, n);

    for(int i = 1; i <= m; i++)

    {

    	int opt, l, r;

    	scanf("%d%d%d", &opt, &l, &r);

    	if(l > r) swap(l, r);

    	if(opt) printf("%lld\n", query(root, l, r));

    	else change(root, l, r);

	}

 	return 0;

}

巴特西

题解【luoguP4145 上帝造题的七分钟2（花神游历各国）】

最新文章

热门文章