本文主要是介绍【线段数】[LUOGU 上帝造题的七分钟2 / 花神游历各国] 线段树/分块 区间开方，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
题目链接：[LUOGU 上帝造题的七分钟2 / 花神游历各国]
题解：
这个题其实在之前我写的数列分块中的有一道题很一样，几乎一模一样了，也是让区间开方，分块写就很好理解，然后现在用线段树写其实大体上的解是一样的但是呢，就是套路不是很一样，，，
这个题重要的就是在一点，对于要好多次开方的数，你会发现，一个在1e12之内的数你对它开最多开方（下取整）六次即可开到1,或者是0，这样的话如果是开到1或者0的数就不用对他再进行处理，跳过即可。这里就可以很好的优化线段树（分块）的复杂度了。
（盗了某某dalao的图，，，－＝≡ヘ(*・ω・)ノ逃）
（还不知道树状数组能不能写，回去学完了再看看，，，，）
代码：
线段树：
#include<bits/stdc++.h>
#define int long long
#define lk k<<1
#define rk k<<1|1
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1; ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e5+7;
struct hit{int l,r,w,max;}tr[sea*4];
int n,m,a[sea];
void build(int k,int l,int r)
{tr[k].l=l,tr[k].r=r;if(l==r){tr[k].max=tr[k].w=read(); return ;}int mid=(l+r)/2;build(lk,l,mid); build(rk,mid+1,r);tr[k].w=tr[lk].w+tr[rk].w;tr[k].max=max(tr[lk].max,tr[rk].max);
}
void alter(int k,int x,int y)
{int l=tr[k].l,r=tr[k].r;if(l==r){tr[k].w=sqrt(tr[k].w); tr[k].max=sqrt(tr[k].max);return;}int mid=(l+r)/2;if(x<=mid&&tr[lk].max>1) alter(lk,x,y); if(y>mid&&tr[rk].max>1) alter(rk,x,y);tr[k].w=tr[lk].w+tr[rk].w;tr[k].max=max(tr[lk].max,tr[rk].max);
}
int ask(int k,int x,int y)
{int l=tr[k].l,r=tr[k].r;if(x<=l&&r<=y) return tr[k].w;int mid=(l+r)/2; int ans=0;if(x<=mid) ans+=ask(lk,x,y); if(y>mid) ans+=ask(rk,x,y);return ans;
}
signed main()
{n=read(); build(1,1,n);m=read(); for(int i=1;i<=m;i++){int s=read(),x=read(),y=read();if(y<=x) swap(x,y);if(s==0) alter(1,x,y);else printf("%lld\n",ask(1,x,y));}return 0;
}
分块
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e5+7;
int block,num,n,m,belong[sea],l[sea],r[sea];
LL ans=0,a[sea],ins[sea],sum[sea];
void build()
{block=sqrt(n); num=n/block; if(n%block) num++;for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;r[num]=n;for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1,sum[belong[i]]+=a[i];
}
void kfbl(int x)//分块暴力（缩写）
{if(ins[x]) return;ins[x]=1;//标记数组sum[x]=0;//整块赋值为0for(int i=l[x];i<=r[x];i++){a[i]=sqrt(a[i]),sum[x]+=a[i];//对于整块的分解，无限开方，但是如果有1或者0就记录下来每次跳过即可if(a[i]>1) ins[x]=0;}
}
void alter_kf(int x,int y)
{if(belong[x]==belong[y])for(int i=x;i<=y;i++) sum[belong[x]]-=a[i],a[i]=sqrt(a[i]),sum[belong[x]]+=a[i];//要记得先删除在修改最后添加else{for(int i=x;i<=r[belong[x]];i++) sum[belong[x]]-=a[i],a[i]=sqrt(a[i]),sum[belong[x]]+=a[i];for(int i=belong[x]+1;i<belong[y];i++) kfbl(i);for(int i=l[belong[y]];i<=y;i++) sum[belong[y]]-=a[i],a[i]=sqrt(a[i]),sum[belong[y]]+=a[i];}
}
LL ask(int x,int y)
{LL ans=0;if(belong[x]==belong[y])for(int i=x;i<=y;i++) ans+=a[i];else{for(int i=x;i<=r[belong[x]];i++) ans+=a[i];for(int i=belong[x]+1;i<belong[y];i++) ans+=sum[i];for(int i=l[belong[y]];i<=y;i++) ans+=a[i];}return ans;
}
int main()
{n=read();for(int i=1;i<=n;i++) scanf("%lld",&a[i]);;build(); m=read();for(int i=1;i<=m;i++){int s=read(),x=read(),y=read(); ans=0;if(x>y) swap(x,y); if(s==0) alter_kf(x,y);else printf("%lld\n",ask(x,y));}return 0;
}
树状数组
（马上补，，，，，）
Continue……
这篇关于【线段数】[LUOGU 上帝造题的七分钟2 / 花神游历各国] 线段树/分块 区间开方的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
