本文主要是介绍线段树+暴力区修 P4145 上帝造题的七分钟 2 / 花神游历各国，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
https://www.luogu.com.cn/problem/P4145
这道题着实想了好久，本来想的是用数学方法找规律，结果写了好久，发现想假了，于是只好看思路，暴力区修！原因是被开根号一定次数就会变成1，是有限的，所以可以暴力区间修改，但是要优化一下，这里直接贴代码。
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5+10;
#define int long long
#define lc u<<1
#define rc u<<1|1
int n,m;
int a[N];
#define endl '\n'
struct Tree{int l,r;int sum,mx;
}tr[N*4];void pushup(int u){tr[u].sum=tr[lc].sum+tr[rc].sum;tr[u].mx=max(tr[lc].mx,tr[rc].mx);
}void build(int u,int l,int r){tr[u]={l,r,a[l],a[l]};if(l==r) return;int m=(l+r)>>1;build(lc,l,m);build(rc,m+1,r);pushup(u);
}void update(int u,int l,int r){if(tr[u].mx==1) return;//优化1 如果最大值已经是1了说明没得开根，直接返回if(tr[u].l==tr[u].r){//优化2，直接在遍历的过程中直接拿了tr[u].sum=sqrt(tr[u].sum);tr[u].mx=sqrt(tr[u].mx);return;}int m=(tr[u].l+tr[u].r)>>1;if(l<=m) update(lc,l,r);if(r>m) update(rc,l,r);pushup(u);
}int query(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u].sum;}int m=(tr[u].l+tr[u].r)>>1;int num=0;if(l<=m) num+=query(lc,l,r);if(r>m) num+=query(rc,l,r);return num;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>a[i];build(1,1,n);cin>>m;//cout<<endl;//cout<<tr[1].ans<<endl;//cout<<endl;while(m--){int op,x,y;cin>>op>>x>>y;if(x>y) swap(x,y);if(op==0){update(1,x,y);}else{cout<<query(1,x,y)<<endl;}}//cout<<endl;//cout<<tr[1].ans<<endl;//for(int i=1;i<=n;++i) cout<<tr[1].ans<<endl;return 0;
}这篇关于线段树+暴力区修 P4145 上帝造题的七分钟 2 / 花神游历各国的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
