【bzoj3211】花神游历各国&&【bzoj3038】上帝造题的七分钟2
2024-08-26 06:47:19
bzoj3038】上帝造题的七分钟2
Description
XLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。
“第一分钟,X说,要有数列,于是便给定了一个正整数数列。
第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟,k说,要能查询,于是便有了求一段数的和的操作。
第四分钟,彩虹喵说,要是NOIP难度,于是便有了数据范围。
第五分钟,诗人说,要有韵律,于是便有了时间限制和内存限制。
第六分钟,和雪说,要省点事,于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。”
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。
Input
第一行一个整数n,代表数列中数的个数。
第二行n个正整数,表示初始状态下数列中的数。
第三行一个整数m,表示有m次操作。
接下来m行每行三个整数k,l,r,k=0表示给[l,r]中的每个数开平方(下取整),k=1表示询问[l,r]中各个数的和。
Output
对于询问操作,每行输出一个回答。
Sample Input
10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8
Sample Output
19
7
6
7
6
HINT
1:对于100%的数据,1<=n<=100000,1<=l<=r<=n,数列中的数大于0,且不超过1e12。
2:数据不保证L<=R 若L>R,请自行交换L,R,谢谢!
——————————————————————————————————————
两道题题面几乎一样就放在一起讲了(其实代码也是一样的2333)
学了一波线段树的区间开根号QAQ
其实没什么特别的如果整个区间都是0或者1 就不做修改 这个可以开个标记记一下
否则就只能暴力单点修改了 似乎并查集维护一波区间是否全0或1也可以???
贴一波代码咯
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
LL read(){
LL ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
LL n,m,L,R,k;
struct node{LL sum,f;}tr[];
void up(int x){
tr[x].sum=tr[x<<].sum+tr[x<<^].sum;
tr[x].f=tr[x<<].f&tr[x<<^].f;
}
void build(int x,int l,int r){
if(l==r){
tr[x].sum=read();
if(tr[x].sum==||tr[x].sum==) tr[x].f=;
return ;
}
int mid=(l+r)>>;
build(x<<,l,mid); build(x<<^,mid+,r);
up(x);
}
void modify(int x,int l,int r){
if(tr[x].f) return ;
if(L<=l&&l==r&&r<=R){
tr[x].sum=(LL)sqrt(tr[x].sum);
if(tr[x].sum==||tr[x].sum==) tr[x].f=;
return ;
}
int mid=(l+r)>>;
if(L<=mid) modify(x<<,l,mid);
if(R>mid) modify(x<<^,mid+,r);
up(x);
}
LL query(int x,int l,int r){
if(L<=l&&r<=R) return tr[x].sum;
LL sum=;
int mid=(l+r)>>;
if(L<=mid) sum+=query(x<<,l,mid);
if(R>mid) sum+=query(x<<^,mid+,r);
return sum;
}
int main()
{
n=read(); build(,,n);
m=read();
for(int i=;i<=m;i++){
k=read(); L=read(); R=read();
if(L>R) swap(L,R);
if(k==) printf("%lld\n",query(,,n));
else modify(,,n);
}
return ;
}
最新文章
- CSS样式基础总结
- nw.js 软件推荐:AxeSlide斧子演示:PPT的另一种可能(转)
- HDU 4738 Caocao&#39;s Bridges(Tarjan)
- iis 访问网站需要进行身份验证
- chroot详解
- oracle触发器书写方法
- Maven(一)
- DB2中的转义字符
- AngularJs学习笔记--Guide教程系列文章索引
- How to: Run Tests from Microsoft Visual Studio
- polygonal approximation
- 转:Android软件开发之PreferenceActivity中的组件
- Dagger2学习笔记
- Mac通过brew安装reds、memcached
- Web前后端分离
- Lucene 09 - 什么是Lucene的高亮显示 + Java API实现高亮显示
- 渗透测试学习 四、 HTML基础
- 微软BI 之SSAS 系列 - 维度的优化,灌木丛属性关系,以及自然层次结构与非自然层次结构的概念
- 【转】win中IDLE选择virtualenv的启动方法
- 关于RNA-Seq数据去接头(Adapter)这事需要讲一讲