HDU 4027

• 剪枝:开方等于7次,值等1
• 以为每个点的值不一样,所以开方是要每个点开方,不能延迟标记
• long long存sum
• 看别人博客:x居然可以>y

  #include <iostream>
  #include <string.h>
  #include <cmath> 
  using namespace std;
  const int maxn = 1e5+5;
  struct segementTree {
  	int left, right;
  	long long sum;
  	#define left(x) tree[x].left
  	#define right(x) tree[x].right
  	#define sum(x) tree[x].sum
  } tree[4*maxn];
  int n,m;
  void build(int p,int left,int right) {
  	left(p) = left; right(p) = right;
  	if (left == right) {
  		cin >> sum(p); return;
  	}
  	int mid = (left + right) / 2;
  	build(2*p,left,mid);
  	build(2*p+1,mid+1,right);
  	sum(p) = sum(2*p) + sum(2*p+1);
  }
  void update(int p, int left, int right) { //由于每个点的值不一样,所有开方要更新每一个点,不能打延迟标记
  	// 当更新7次以上,值就为1,那么剪枝，即使add()>=1也不用管该节点的子树
  	if (sum(p) == right(p) - left(p) + 1) return;
  	if (left(p) == right(p)) {
  		sum(p) = sqrt(1.0 * sum(p));
  		return;
  	}
  	int mid = (left(p) + right(p)) / 2;
  	if (left <= mid) update(2*p,left,right);
  	if (mid < right) update(2*p+1,left,right);
  	sum(p) = sum(2*p) + sum(2*p+1);
  }
  long long query(int p,int left,int right) {
  	if (left <= left(p) && right(p) <= right) return sum(p);
  	int mid = (left(p) + right(p)) / 2;
  	long long res = 0;
  	if (left <= mid) res+=query(2*p,left,right);
  	if (mid < right) res+=query(2*p+1,left,right);
  	return res;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	int cnt = 0;
  	while (scanf("%d",&n) != EOF) {
  		build(1,1,n);
  		scanf("%d",&m);
  		printf("Case #%d:\n",++cnt);
  		int t, x, y;
  		for (int i = 1; i <= m; i++) {
  			scanf("%d%d%d",&t,&x,&y);
  			if (x > y) { int temp = x; x = y; y = temp; }
  			if (t) printf("%lld\n",query(1,x,y));
  			else update(1,x,y);
  		}
  		printf("\n");
  	}
  	return 0;
  }