Bzoj3211花神游历各国

提供一种数据结构，支持区间求和，以及区间开根号。

这种题一般暴力谁都能打，主要是练线段树。

下面给出两种解法：

第一种，额外维护区间最大值。

由于1、0开根是其本身，开根没有意义，我们维护区间最大值，如果区间最大值已经为1或0则直接return，否则继续向下开根。

剩下的维护区间和就可以了。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define ll long long 
using namespace std;
struct Sengment_Tree{int l,r;ll sum,maxn;
}t[400200];
int n,m;
ll read(){ll sum=0;int f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-') f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}return sum*f;
}
void updata(int p){t[p].sum=t[p<<1].sum+t[p<<1|1].sum;t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
}
void build(int p,int l,int r){t[p].l=l;t[p].r=r;if(l==r){t[p].sum=t[p].maxn=read();return;}int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);updata(p);
}
void change(int p,int l,int r){if(t[p].maxn<=1) return ;if(t[p].l==t[p].r){t[p].sum=t[p].maxn=(ll)sqrt(t[p].sum);return ;}int mid=t[p].l+t[p].r>>1;if(l<=mid) change(p<<1,l,r);if(r>mid) change(p<<1|1,l,r);updata(p);
}
ll ask(int p,int l,int r){if(l<=t[p].l&&t[p].r<=r) return t[p].sum;int mid=t[p].l+t[p].r>>1;ll ans=0;if(l<=mid) ans+=ask(p<<1,l,r);if(r>mid) ans+=ask(p<<1|1,l,r);return ans;
}
int main(){int x,y,z;n=read();build(1,1,n);m=read();for(int i=1;i<=m;i++){x=read();y=read();z=read();if(x==1) printf("%lld\n",ask(1,y,z));else change(1,y,z);}return 0;
}

View Code

第二种，维护lazy，表示是否已经全是1或0。

如果是，则直接return，否则继续向下开根。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define ll long long 
using namespace std;
struct Sengment_Tree{int l,r,flag;ll sum;
}t[400200];
ll read(){ll sum=0;int f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-') f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}return sum*f;
}
int n,qnum;
ll a[100050];
void updata(int p){t[p].sum=t[p<<1].sum+t[p<<1|1].sum;t[p].flag=t[p<<1].flag&t[p<<1|1].flag;
}
void build(int p,int l,int r){t[p].l=l;t[p].r=r;if(l==r){t[p].sum=a[l];if(a[l]==0||a[l]==1)t[p].flag=1;else t[p].flag=0;return ;}int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);updata(p);
}
void change(int p,int l,int r){if(t[p].l==t[p].r){t[p].sum=(ll)sqrt(t[p].sum);if(t[p].sum==0||t[p].sum==1)t[p].flag=1;return ;}int mid=t[p].l+t[p].r>>1;if(l<=mid&&!t[p<<1].flag) change(p<<1,l,r);if(r>mid&&!t[p<<1|1].flag) change(p<<1|1,l,r);updata(p);
}
ll ask(int p,int l,int r){
//    cout<<t[p].sum<<endl;if(l<=t[p].l&&t[p].r<=r) return t[p].sum;int mid=t[p].l+t[p].r>>1;ll ans=0;if(l<=mid) ans+=ask(p<<1,l,r);if(r>mid) ans+=ask(p<<1|1,l,r);return ans;
}
int main(){
//    freopen("out.docx","w",stdout);int x,y,opt;n=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);qnum=read();for(int i=1;i<=qnum;i++){opt=read();x=read();y=read();if(opt==1) printf("%lld\n",ask(1,x,y));else change(1,x,y);}return 0;
}