2018.07.20 bzoj3211: 花神游历各国(线段树)
2024-10-13 13:04:26
传送门
维护区间开方,区间求和。这个是线段树常规操作。
显然一个数被开方若干次之后要么是1,要么是0,所以用线段树维护区间最大和区间和,如果区间最大不超过1就剪枝剪掉,不然就继续递归直到叶节点时停下进行单点修改。
虽然这方法看起来很暴力,但实际上由于只有开方这一个操作,时间复杂度是有保障的。
代码如下:
#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
struct Node{int l,r;ll maxn,sum;}T[N<<2];
ll a[N];
int n,m;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void write(ll x){
if(x>9)write(x/10);
putchar((x%10)^48);
}
inline ll max(ll a,ll b){return a>b?a:b;}
inline void pushup(int p){T[p].maxn=max(T[lc].maxn,T[rc].maxn),T[p].sum=T[lc].sum+T[rc].sum;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){T[p].maxn=T[p].sum=a[l];return;}
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
inline void update(int p,int ql,int qr){
if(T[p].l>qr||T[p].r<ql||T[p].maxn<=1)return;
if(T[p].l==T[p].r){T[p].maxn=T[p].sum=sqrt(T[p].maxn);return;}
if(qr<=mid)update(lc,ql,qr);
else if(ql>mid)update(rc,ql,qr);
else update(lc,ql,mid),update(rc,mid+1,qr);
pushup(p);
}
inline ll query(int p,int ql,int qr){
if(T[p].l>qr||T[p].r<ql)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+1,qr);
}
int main(){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
build(1,1,n);
m=read();
while(m--){
int op=read(),l=read(),r=read();
if(l>r)l^=r,r^=l,l^=r;
switch(op){
case 2:{update(1,l,r);break;}
default:{write(query(1,l,r)),puts("");break;}
}
}
return 0;
}
最新文章
- PSR规范
- js 日期
- JS对象之间的关系
- 三大域对象的使用总结request域 + session域 +
- C++:异常的处理
- yeoman运行grunt serve 提示错误
- AE与AO的区别
- webservice跨服务器上传附件
- vue的Virtual Dom实现- snabbdom解密
- Spring-java-模板设计模式
- How To determine DDIC Check Table, Domain and Get Table Field Text Data For Value?
- 在echarts里在geojson绘制的地图上展示散点图(气泡)、线集。
- ==还款-代偿(csv循环自动代偿)
- 移植busybox构建最小根文件系统
- docker私有仓库pull/push
- IOS 单击手势和cell点击冲突
- mysql的.sql文件头部 /*!32312 IF NOT EXISTS*/;
- Spring Boot 使用IntelliJ IDEA创建一个web开发实例(四)
- oc 第五天(内存管理)
- java线程总结1--线程的一些概念基础以及线程状态