BZOJ 3211 弗洛拉前往国家 树阵+并检查集合-阿里云开发者社区

开发者社区> 云计算> 正文

BZOJ 3211 弗洛拉前往国家 树阵+并检查集合

简介:
 标题效果:弗洛拉看上每个国家,有时候,他会是一个连续的国家访问,求他的胃口和;有时候,他会产生厌恶国家的连续周期。喜欢成为sqrt(x)按四舍五入。

思维:乍一看,这似乎是RMQ问题,线段树将能够使用水太,但是马克如何下游平方根?这是一个严重的问题,所以我们要换一个思路。
注意到开根号有一个有趣的性质:sqrt(1) = 1,sqrt(0) = 0。并且全部的数字经过有限次的开根号运算都会变成1。

这个性质就非常好了。我们对每个点暴力开根号,然后当这个店的点权变成1的时候就打一个标记。下次无论这个点了。用线段树维护。


当然还有常数更小的方法。

对整个序列维护树状数组,利用并查集维护每一个数右边第一个不是1的数字,然后暴力开根号,当一个数字变成1的时候就把这个点在并查集中的父亲连到它右边的数的父亲上。

在改动连续区间的时候就能够跳过连续的1了。



CODE:


#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 200010
using namespace std;

int cnt,asks;
int src[MAX];
long long fenwick[MAX];

int father[MAX];

void Pretreatment();

inline void Fix(int x,int c);
inline void Fix(int x);
inline long long GetSum(int x);

int Find(int x);

int main()
{
	cin >> cnt;
	for(int i = 1;i <= cnt; ++i) {
		scanf("%d",&src[i]);
		Fix(i,src[i]);
		if(src[i] <= 1)	father[i] = i + 1;
	}
	cin >> asks;
	for(int flag,x,y,i = 1;i <= asks; ++i) {
		scanf("%d%d%d",&flag,&x,&y);
		if(flag == 1)
			printf("%lld\n",GetSum(y) - GetSum(x - 1));
		else
			for(x = Find(x);x <= y;x = Find(x + 1)) {
				Fix(x,-src[x]);
				src[x] = sqrt(src[x]) + 1e-7;
				Fix(x,src[x]);
				if(src[x] == 1)	father[x] = Find(x + 1);
			}
	}
	return 0;
}

inline void Fix(int x,int c)
{
	for(int i = x;i <= cnt;i += i&-i)
		fenwick[i] += c;
}

inline long long GetSum(int x)
{
	long long re = 0;
	for(int i = x;i;i -= i&-i)
		re += fenwick[i];
	return re;
}

int Find(int x)
{
	if(!father[x] || father[x] == x)	return father[x]  = x;
	return father[x] = Find(father[x]);	
}


版权声明:本文博客原创文章,博客,未经同意,不得转载。





本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4670859.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章