http://uoj.ac/problem/228 (题目链接)
题意
给出一个序列,维护区间加法,区间开根,区间求和
Solution
线段树。考虑区间开根怎么做。当区间的最大值与最小值相等时,我们直接对整个区间开根。最坏情况下,一次开根的复杂度最坏是${O(n)}$的,然而每次开根可以迅速拉近两个数之间的大小差距,最坏复杂度的开根不会超过${5}$次。
但是考虑这样一种情况:${\sqrt{x+1}=\sqrt{x}+1}$,如果序列长成这样:${65535,65536,65535,65536······}$,那么对它开根${3}$次,每次都是最坏情况下的复杂度,最后变成了${3,4,3,4······}$,如果此时我们对它进行区间加法,又加回${65535,65536,65535,65536······}$,不断循环,复杂度就炸裂了。所以当出现这种情况时,我们也对它进行区间开根。
细节
LL
代码
// uoj228
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define LL long long
#define inf 1ll<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
int n,m,a[maxn];
struct segtree {int l,r;LL mn,mx,tag,s;}tr[maxn<<2]; void update(int k) {
tr[k].mn=min(tr[k<<1].mn,tr[k<<1|1].mn)+tr[k].tag;
tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx)+tr[k].tag;
tr[k].s=tr[k<<1].s+tr[k<<1|1].s+tr[k].tag*(tr[k].r-tr[k].l+1);
}
void build(int k,int s,int t) {
tr[k].l=s;tr[k].r=t;
int mid=(s+t)>>1;
if (s==t) {tr[k].mn=tr[k].mx=tr[k].s=a[s];return;}
build(k<<1,s,mid);
build(k<<1|1,mid+1,t);
update(k);
}
void add(int k,int s,int t,int val) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (l==s && r==t) {tr[k].s+=(LL)val*(tr[k].r-tr[k].l+1);tr[k].mn+=val,tr[k].mx+=val;tr[k].tag+=val;return;}
if (t<=mid) add(k<<1,s,t,val);
else if (s>mid) add(k<<1|1,s,t,val);
else add(k<<1,s,mid,val),add(k<<1|1,mid+1,t,val);
update(k);
}
void Sqrt(int k,int s,int t,LL tag) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (l==s && r==t) {
if ((tr[k].mx==tr[k].mn) || (tr[k].mn+1==tr[k].mx && floor(sqrt(tr[k].mn+tag))+1==floor(sqrt(tr[k].mx+tag)))) {
LL tmp=floor(sqrt(tr[k].mn+tag))-tr[k].mn-tag;
tr[k].tag+=tmp;tr[k].mn+=tmp;tr[k].mx+=tmp;
tr[k].s+=(tr[k].r-tr[k].l+1)*tmp;
return;
}
}
if (t<=mid) Sqrt(k<<1,s,t,tag+tr[k].tag);
else if (s>mid) Sqrt(k<<1|1,s,t,tag+tr[k].tag);
else Sqrt(k<<1,s,mid,tag+tr[k].tag),Sqrt(k<<1|1,mid+1,t,tag+tr[k].tag);
update(k);
}
LL query(int k,int s,int t) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (l==s && r==t) return tr[k].s;
if (t<=mid) return query(k<<1,s,t)+tr[k].tag*(t-s+1);
else if (s>mid) return query(k<<1|1,s,t)+tr[k].tag*(t-s+1);
else return query(k<<1,s,mid)+query(k<<1|1,mid+1,t)+tr[k].tag*(t-s+1);
} int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for (int op,l,r,val,i=1;i<=m;i++) {
scanf("%d%d%d",&op,&l,&r);
if (op==1) scanf("%d",&val),add(1,l,r,val);
if (op==2) Sqrt(1,l,r,0);
if (op==3) printf("%lld\n",query(1,l,r));
}
return 0;
}
【uoj228】 基础数据结构练习题的更多相关文章
-
uoj228 基础数据结构练习题
趁别人题解没有放出来赶快写一篇 整数序列,操作 区间加 区间变成sqrt(下取整) 区间和 考虑一下对于每个区间里所有sqrt不同的段操作,那么可以在O(段数logn)一次的时间内完成sqrt操作.考 ...
-
[UOJ228] 基础数据结构练习题 - 线段树
考虑到一个数开根号 \(loglog\) 次后就会变成1,设某个Node的势能为 \(loglog(maxv-minv)\) ,那么一次根号操作会使得势能下降 \(1\) ,一次加操作最多增加 \(l ...
-
【UOJ228】基础数据结构练习题(线段树)
[UOJ228]基础数据结构练习题(线段树) 题面 UOJ 题解 我们来看看怎么开根? 如果区间所有值都相等怎么办? 显然可以直接开根 如果\(max-sqrt(max)=min-sqrt(min)\ ...
-
【UOJ#228】基础数据结构练习题 线段树
#228. 基础数据结构练习题 题目链接:http://uoj.ac/problem/228 Solution 这题由于有区间+操作,所以和花神还是不一样的. 花神那道题,我们可以考虑每个数最多开根几 ...
-
uoj #228. 基础数据结构练习题 线段树
#228. 基础数据结构练习题 统计 描述 提交 自定义测试 sylvia 是一个热爱学习的女孩子,今天她想要学习数据结构技巧. 在看了一些博客学了一些姿势后,她想要找一些数据结构题来练练手.于是她的 ...
-
【线段树】uoj#228. 基础数据结构练习题
get到了标记永久化 sylvia 是一个热爱学习的女孩子,今天她想要学习数据结构技巧. 在看了一些博客学了一些姿势后,她想要找一些数据结构题来练练手.于是她的好朋友九条可怜酱给她出了一道题. 给出一 ...
-
UOJ228:基础数据结构练习题——题解
http://uoj.ac/problem/228 参考:https://www.cnblogs.com/ljh2000-jump/p/6357583.html 考虑当整个区间的最大值开方==最小值开 ...
-
uoj228:基础数据结构练习题
题意:http://uoj.ac/problem/228 sol :线段树开根操作 对于节点x,可以在max[x]-min[x]<=1时直接做,转化为区间减或区间覆盖 #include< ...
-
UOJ228 简单数据结构练习题
Description 传送门 维护一个数列, 有以下操作: 对[l,r]同时加上x 把[l,r]开根后下取整. 查询[l,r]之和 n,m \(\leq\)$ 100000, $\(a_i,x \l ...
随机推荐
-
基于单决策树的AdaBoost
①起源:Boosting算法 Boosting算法的目的是每次基于全部数据集,通过使用同一种分类器不同的抽取参数方法(如决策树,每次都可以抽取不同的特征维度来剖分数据集) 训练一些不同弱分类器(单次分 ...
-
UVA11038- How Many O&;#39;s?(组合数学)
题目链接 题意:求出在a到b之间的数中,有多少个0. 思路:组合数学问题.能够枚举每一个位置上的数i,如果i之前的数为left,后面的为right,后面有num位数.当i != 0时,将i置为0,所以 ...
-
iOS - 第三方框架 - AFN
#5.AFNetworking 2.6使用方法 >2.6版本 支持 iOS7以上,而且支持NSURLConnectionOperation >3.0版本 支持 iOS7以上 NSURLCo ...
-
C#中object sender,EventHandler e有个毛作用
button1_Click(object sender,EventHandler e) { Button button=(Button)sender; button.Text="text p ...
-
彻底卸载 RAD Studio 2009/2010/XE+ 的步骤
重新安装 RAD 系列时,建议将上一个版本彻底卸载,彻底卸载 RAD Studio 2009/2010/XE+ 的步骤: 控制面板-->添加/删除程序中执行了卸载操作以后, 还需要做以下工作: ...
-
java基础(8) -集合类-Collecion
集合类-Collecion Collection接口 常用方法 //添加新元素 boolean add (E element); //返回迭代器 Iterator<E> iterator( ...
-
python中星号的意义(**字典,*列表或元组)
传递实参和定义形参(所谓实参就是调用函数时传入的参数,形参则是定义函数是定义的参数)的时候,你还可以使用两个特殊的语法:*.** . 调用函数时使用* ,** test(*args)中 * 的作用:其 ...
-
HBase基本概念与基本使用
1. HBase简介 1.1 什么是HBase HBASE是一个高可靠性.高性能.面向列.可伸缩的分布式存储系统,利用HBASE技术可在廉价PC Server上搭建起大规模结构化存储集群. HBASE ...
-
2.03-handler_openner
import urllib.request def handler_openner(): #系统的urlopen并没有添加代理的功能所以需要我们自定义这个功能 #安全 套接层 ssl第三方的CA数字证 ...
-
Django的路由层
U RL配置(URLconf)就像Django 所支撑网站的目录.它的本质是URL与要为该URL调用的视图函数之间的映射表:你就是以这种方式告诉Django,对于客户端发来的某个URL调用哪一段逻辑代 ...