最近写kuangbin专题，碰到的题记录一下

HDU-4027-Can you answer these queries?（add的其他作用）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027

题目大意：n个数，两种操作，0.将[l,r]内的所有数开平方（四舍五入取ll），1.求[l,r]内的sum

思路：线段树板子，首先需要更新到最下面，1开平方还是1，所以一个数最多更新64次，然后记录一下是否需要开平发即可。

AC：

const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);

ll tree[MAXN<<2],add[MAXN<<2];
int n;

void build_tree(int l,int r,int rt){
	if(l==r){
		scanf("%lld",&tree[rt]);
		if(tree[rt]!=1)	add[rt]=1;
		return ;
	}int mid=(l+r)>>1;
	build_tree(l,mid,rt<<1);
	build_tree(mid+1,r,rt<<1|1);
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
	if(add[rt<<1]||add[rt<<1|1])	add[rt]=1;
	else							add[rt]=0;
}
ll Query(int ql,int qr,int l,int r,int rt){
	if(ql<=l&&r<=qr){
		return tree[rt];
	}int mid=(l+r)>>1;
	ll res=0;
	if(ql<=mid)	res+=Query(ql,qr,l,mid,rt<<1);
	if(qr>mid)	res+=Query(ql,qr,mid+1,r,rt<<1|1);
	return res;
}
void updata(int ql,int qr,int l,int r,int rt){
	if(add[rt]==0){
		return ;
	}
	if(l==r){//到底了&&不为1 
		tree[rt]=sqrt(double(tree[rt]));
		if(tree[rt]==1)	add[rt]=0;
		return ;
	}int mid=(l+r)>>1;
	if(ql<=mid)	updata(ql,qr,l,mid,rt<<1);
	if(qr>mid)	updata(ql,qr,mid+1,r,rt<<1|1);
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
	if(add[rt<<1]||add[rt<<1|1])	add[rt]=1;
	else							add[rt]=0;
}
int main(){
	int Case=1;
	while(scanf("%d",&n)!=EOF){
		printf("Case #%d:\n",Case++);
		clean(add,0);
		build_tree(1,n,1);
		int m;scanf("%d",&m);
		ll oper,a,b;
		for(int i=1;i<=m;++i){
			scanf("%lld%lld%lld",&oper,&a,&b);
			if(a>b)	swap(a,b);
			if(oper){//查询 
				printf("%lld\n",Query(a,b,1,n,1));
			}
			else{//修改 
				updata(a,b,1,n,1);
			}
		}printf("\n");
	}
}