题解 SP2713 【GSS4 - Can you answer these queries IV】
King丨帝御威
2019-01-06 22:09:58
第一眼，一点头绪都没有，因为涉及到区间修改和查询，像线段树，但又一副不可做的样子，因为如果区间修改不加任何优化的话，常数就会大的一批，应该会超时，那么，我们就来考虑关于开方的有关性质，首先$sqrt(1)=1$，震惊！！没错，这就是修改终点，如果一个位置的数为1，再开方是没有意义的，那么我们就可以维护一个区间最大值，如果这个区间最大值是$1$，也就是这个区间的数都是$1$，那么就没必要进行修改了，区间求和的话就跟普通线段树没什么区别了。还有，为什么区间修改时终点是$l==r$呢？难道不是$L<=l$&&$r<=R$么？因为这里的区间修改是采用了一种暴力的思想，也就是一个一个改，相当于单点修改。
如果不知道怎么写的话，可以参考以下代码：
``` cpp
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>
#define maxn 100007
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
int n,m,tim;
ll maxx[maxn<<2],sum[maxn<<2];
inline ll qread() {
char c=getchar();ll num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
inline void pushup(int rt) {
sum[rt]=sum[ls]+sum[rs];
maxx[rt]=max(maxx[ls],maxx[rs]);
}
void build(int rt, int l, int r) {
if(l==r) {
sum[rt]=maxx[rt]=qread();
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
void modify(int rt, int l, int r, int L, int R) {
if(l==r) {
sum[rt]=sqrt(sum[rt]);
maxx[rt]=sqrt(maxx[rt]);
return;
}
int mid=(l+r)>>1;
if(L<=mid&&maxx[ls]>1) modify(ls,l,mid,L,R);
if(R>mid&&maxx[rs]>1) modify(rs,mid+1,r,L,R);
pushup(rt);
}
ll csum(int rt, int l, int r, int L, int R) {
if(L>r||R<l) return 0;
if(L<=l&&r<=R) return sum[rt];
int mid=(l+r)>>1;
return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R);
}
int main() {
while(scanf("%d",&n)==1) {
printf("Case #%d:\n",++tim);
build(1,1,n);
m=qread();
for(int i=1,k,x,y;i<=m;++i) {
k=qread(),x=qread(),y=qread();
if(x>y) swap(x,y);
if(!k) modify(1,1,n,x,y);
else printf("%lld\n",csum(1,1,n,x,y));
}
}
return 0;
}
```
希望这篇题解对大家理解线段树能有所帮助。