【BZOJ】【P 3211】【花神遊歴各国】【題解】【線分樹】

#include<cstdio>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define L i<<1
#define R i<<1|1
using namespace std;
const int maxn=100010;
typedef long long lld;
lld a[maxn];
	struct node{
		lld sum,sure;
		node(){
			sum=sure=0;
		}
	};
	node t[maxn<<2];
struct seg_tree{
	void rz(lld i){
		t[i].sum=t[L].sum+t[R].sum;
		t[i].sure=t[R].sure&&t[L].sure;
	}
	void build(lld i,lld l,lld r){
		if(l==r){
			t[i].sum=a[l];
			t[i].sure=a[l]==0||a[l]==1;
			return;
		}
		lld mid=l+r>>1;
		build(lson);
		build(rson);
		rz(i);
	}
	void Change(lld i,lld l,lld r,lld l0,lld r0){
		if(t[i].sure)
			return;
		if(l==r){
			t[i].sum=(lld)sqrt(t[i].sum)+0.001;
			if(t[i].sum==0||t[i].sum==1)
				t[i].sure=1;
			return ;
		}
		lld mid=l+r>>1;
		if(l0<=mid)Change(lson,l0,r0);
		if(r0>mid) Change(rson,l0,r0);
		rz(i);
	}
	lld qsum(lld i,lld l,lld r,lld l0,lld r0){
		if(l0<=l&&r0>=r)
			return t[i].sum;
		lld mid=l+r>>1;
		lld ans=0;
		if(l0<=mid)ans+=qsum(lson,l0,r0);
		if(r0>mid) ans+=qsum(rson,l0,r0);
		return ans;
	}
}T;
lld getlld(){
	lld res=0,ok=0;char ch;
	while(1){
		ch=getchar();
		if(isdigit(ch)){
			res*=10;res+=ch-'0';ok=1;
		}else if(ok)break;
	}return res;
}
lld n,m;
int main(){
	n=getlld();
	for(lld i=1;i<=n;i++)a[i]=getlld();
	T.build(1,1,n);
	m=getlld();
	while(m--){
		lld opt=getlld();
		if(opt==1){
			lld l=getlld(),r=getlld();
			printf("%I64d
",T.qsum(1,1,n,l,r));
		}else{
			lld l=getlld(),r=getlld();
			T.Change(1,1,n,l,r);
		}
	}
	return 0;
}