P4145 上帝造题的七分钟 2 / 花神游历各国
XichenOC
·
·
题解
P4145 上帝造题的七分钟 2 / 花神游历各国
题目大意：
本体总共就两个操作：
$2.$输出$l$至$r$区间内的所有数的和
# 思路：
既然是区间修改和区间查询，那~~是个蒟蒻~~都能想到用线段树来维护，但我们可以发现，若一个根节点的子树开方了，那它的和也变得不确定。因此不能用懒标记来实现区间修改。可单点修改的复杂度为$n^2$，一看就会超。但是，我们又双叒叕发现一个数顶多开$5$次方就会变为$1$或$0$（ $\sqrt {\sqrt{\sqrt{\sqrt{\sqrt{\sqrt {10^{12}}}}}}} \approx 1$ ）而正好$\sqrt 1=1$，所以我们只需要再维护一个区间最大值，在进行更新时看是否大于$1$，若大于的话才需要更新
# 完整代码：
```cpp
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int N=101000;
int a[N];
struct edge{
int sum,max;
}tr[4*N];
inline int read(){
int x=0,w=1;
char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
void build(int p,int l,int r){
if(l==r){
tr[p].sum=a[l];
tr[p].max=a[l];
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
tr[p].sum=tr[lc].sum+tr[rc].sum;
tr[p].max=max(tr[lc].max,tr[rc].max);
}
void update(int p,int l,int r,int ll,int rr){
if(l==r && ll<=l && r<=rr){
tr[p].sum=sqrt(tr[p].sum);
tr[p].max=tr[p].sum;
return;
}
int mid=(l+r)>>1;
if(mid>=ll && tr[lc].max>1)update(lc,l,mid,ll,rr);
if(mid<rr && tr[rc].max>1)update(rc,mid+1,r,ll,rr);
tr[p].sum=tr[lc].sum+tr[rc].sum;
tr[p].max=max(tr[lc].max,tr[rc].max);
}
int query(int p,int l,int r,int ll,int rr){
if(ll<=l && r<=rr){
return tr[p].sum;
}
int res=0;
int mid=(l+r)>>1;
if(mid>=ll)res+=query(lc,l,mid,ll,rr);
if(mid<rr)res+=query(rc,mid+1,r,ll,rr);
return res;
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
a[i]=read();
}
build(1,1,n);
int m;
cin>>m;
int k,l,r;
for(int i=1;i<=m;++i){
k=read(),l=read(),r=read();
if(l>r)swap(l,r);
if(k==0)update(1,1,n,l,r);
else printf("%lld\n",query(1,1,n,l,r));
}
}
```
[**线段树讲解**](https://www.luogu.com.cn/article/ojh62kc0)