博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 3211 弗洛拉前往国家 树阵+并检查集合
阅读量:5256 次
发布时间:2019-06-14

本文共 1609 字,大约阅读时间需要 5 分钟。

 标题效果:弗洛拉看上每个国家,有时候,他会是一个连续的国家访问,求他的胃口和;有时候,他会产生厌恶国家的连续周期。喜欢成为sqrt(x)按四舍五入。
思维:乍一看,这似乎是RMQ问题,线段树将能够使用水太,但是马克如何下游平方根?这是一个严重的问题,所以我们要换一个思路。
注意到开根号有一个有趣的性质:sqrt(1) = 1,sqrt(0) = 0。并且全部的数字经过有限次的开根号运算都会变成1。

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

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

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

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

CODE:

#include 
#include
#include
#include
#include
#define MAX 200010using 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]); }

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

转载于:https://www.cnblogs.com/mfrbuaa/p/4670859.html

你可能感兴趣的文章
android smack MultiUserChat.getHostedRooms( NullPointerException)
查看>>
[置顶] Linux终端中使用上一命令减少键盘输入
查看>>
03 线程池
查看>>
设计模式课程 设计模式精讲 2-2 UML类图讲解
查看>>
Silverlight 的菜单控件。(不是 Toolkit的)
查看>>
jquery的contains方法
查看>>
linux后台运行和关闭SSH运行,查看后台任务
查看>>
桥接模式-Bridge(Java实现)
查看>>
303. Range Sum Query - Immutable
查看>>
C# Dynamic通用反序列化Json类型并遍历属性比较
查看>>
前台freemark获取后台的值
查看>>
Spring-hibernate整合
查看>>
exit和return的区别
查看>>
Django 相关
查看>>
Python(软件目录结构规范)
查看>>
codeforces水题100道 第二十二题 Codeforces Beta Round #89 (Div. 2) A. String Task (strings)
查看>>
c++||template
查看>>
条件断点 符号断点
查看>>
.net学习之继承、里氏替换原则LSP、虚方法、多态、抽象类、Equals方法、接口、装箱拆箱、字符串------(转)...
查看>>
python的多行注释
查看>>