本文共 1983 字，大约阅读时间需要 6 分钟。
线段树裸题，但是由于是开平方根，所以只能暴力单点修改
但是，光这么做会T，当单点值为0或1是就不会变了。
于是可以给区间打上标记，有标记就不递归下去修改了。AC
#include #include #include #include #include #include #include #include #include #include #include #include #define rre(i,r,l) for(int i=(r);i>=(l);i--)#define re(i,l,r) for(int i=(l);i<=(r);i++)#define Clear(a,b) memset(a,b,sizeof(a))#define inout(x) printf("%d",(x))#define douin(x) scanf("%lf",&x)#define strin(x) scanf("%s",(x))#define LLin(x) scanf("%lld",&x)#define op operator#define CSC maintypedef unsigned long long ULL;typedef const int cint;typedef long long LL;using namespace std;void inin(int &ret){ ret=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar(); ret=f?-ret:ret;}LL sum[400010];int l[400010],n,m,r[400010],bo[400040];LL a[100010];void build(int k,int ll,int rr){ l[k]=ll,r[k]=rr; if(ll==rr){sum[k]=a[ll];if(sum[k]==0||sum[k]==1)bo[k]=1;return ;} int mid=(ll+rr)>>1; build(k<<1,ll,mid); build(k<<1|1,mid+1,rr); sum[k]=sum[k<<1]+sum[k<<1|1],bo[k]=bo[k<<1]&bo[k<<1|1];}LL query(int k,int ll,int rr){ if(l[k]>=ll&&r[k]<=rr)return sum[k]; int mid=(l[k]+r[k])>>1; if(rr<=mid)return query(k<<1,ll,rr); if(ll>mid)return query(k<<1|1,ll,rr); return query(k<<1,ll,rr)+query(k<<1|1,ll,rr);}void change(int k,int ll,int rr){ if(bo[k])return ; if(l[k]==r[k]){sum[k]=sqrt(sum[k]);if(sum[k]==0||sum[k]==1)bo[k]=1;return ;} int mid=(l[k]+r[k])>>1; if(rr<=mid)change(k<<1,ll,rr); else if(ll>mid)change(k<<1|1,ll,rr); else change(k<<1,ll,rr),change(k<<1|1,ll,rr); sum[k]=sum[k<<1]+sum[k<<1|1],bo[k]=bo[k<<1]&bo[k<<1|1];}int CSC(){ inin(n); re(i,1,n)LLin(a[i]); build(1,1,n); inin(m); re(i,1,m) { int opt,aa,bb;inin(opt),inin(aa),inin(bb); if(aa>bb)swap(aa,bb); if(opt==1)printf("%lld\n",query(1,aa,bb)); else change(1,aa,bb); } return 0;}
转载于:https://www.cnblogs.com/HugeGun/p/5151148.html