刷题向》关于线段树的区间开根号 BZOJ3211(NORMAL+)
2024-08-29 14:51:43
这是一道关于线段树的区间开根号的裸题,没什么好讲的。
值得注意的是,因为有区间开根号的性质,所以我们每一次更改操作只能把更改区间所覆盖的所有元素全部查找,当然你直接找效率明显爆炸。。。
能够注意到,指数级别的操作一次更改的数字都很大,而题目的数字最大是10的9次,所以可以注意到的是当一个区间更新6遍以后就失去更新的意义了,因为当你更改次数超过6次所有非负整数数字就全部会化为1。所以可以在每一个节点上加一个类似于LAZY标记的东西,记录开根号次数,以便节约跟新时间。
贴出题目&代码
Description
线段树区间开根号与求和
Input
第一行N代表有N个数
第二行有N个数,代表这N个值分别是多少
第三行有一个M
接下来M行,每行有X,L,R
当X为1代表求区间:(L,R)的和。
当X为2代表对区间:(L,R)开根号。
Output
每次x=1时,每行一个整数,表示区间和
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
/**************************************************************
Problem: 3211
User: PencilWang
Language: C++
Result: Accepted
Time:1996 ms
Memory:9036 kb
****************************************************************/ #include<cstdio>
#include<cmath>
int n,m;
struct shit{
int L,R,t;
long long num;
}s[];
int w[];
void push_up(int p)
{
s[p].num=s[p<<].num+s[p<<|].num;
return ;
}
void build(int p,int l,int r)
{
s[p].L=l;
s[p].R=r;
if(l==r)
{
s[p].num=w[l];
return ;
}
int mid=(l+r)>>;
build(p<<,l,mid);
build(p<<|,mid+,r);
push_up(p);
return ;
}
void fuck(int p,int a,int b)
{
if(a<=s[p].L&&s[p].R<=b)
{
s[p].t++;
if(s[p].L==s[p].R)
{
s[p].num=sqrt(s[p].num);
return ;
}
}
int mid=(s[p].L+s[p].R)>>;
if(s[p<<].t<&&a<=mid)fuck(p<<,a,b);
if(s[p<<|].t<&&b>mid)fuck(p<<|,a,b);
push_up(p);
return ;
}
long long Q(int p,int a,int b)
{
if(a<=s[p].L&&s[p].R<=b)
{
return s[p].num;
}
long long ans=;
int mid=(s[p].L+s[p].R)>>;
if(a<=mid) ans+=Q(p<<,a,b);
if(b>mid)ans+=Q(p<<|,a,b);
return ans;
}
int main()
{
int a,b,f;
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",w+i);
scanf("%d",&m);
build(,,n);
while(m--)
{
scanf("%d%d%d",&f,&a,&b);
if(f-)fuck(,a,b);
else printf("%lld\n",Q(,a,b));
}
return ;
}
3211
最新文章
- ASP.NET Core 1.0 使用 Dapper 操作 MySql(包含事务)
- 【GOF23设计模式】装饰模式
- HTML 5 应用程序缓存
- 初学require.js
- hdu 3938 并查集
- WordPress 后台禁用Google Open Sans字体,加速网站
- javascript 关闭窗口,弹出新窗口并带有确认关闭对话框解决办法
- MySQL 基础学习
- ORACLE获取表信息方法
- Linux文件管理下
- linq 在查询表达式中处理异常
- 1.Linux下libevent和memcached安装
- 有限状态机FSM
- 28.Mongodb问题解决
- JavaScript高级编程———基本包装类型String和单体内置对象Math
- 跟厂长学PHP7内核(五):系统分析生命周期
- Android网络编程(一)HTTP协议原理
- 手写代码UI,xib和StoryBoard间的的优劣比较
- Service的学习代码
- django中两张表有外键关系的相互查找方法,自定义json编码方法
热门文章
- HihoCoder 1104 : Suzhou Adventure(树形DP)
- Django json处理
- Bean后置处理器 BeanPostProcessor
- PHP Tools for VS2017 key/破解 [搬运]
- Java面试题:如何对HashMap按键值排序
- module_param 用于动态开启/关闭 驱动打印信息
- XAMPP配置8080端口
- form表单使用(博客系统的登陆验证,注册)
- CGI/MIME/servlet术语解释
- linux lcd设备驱动剖析三