HDU_4027_セグメントツリー区間開方

HDU 4027

枝切り:開方は7回、値など1

は、各点の値が異なると判断するので、開方は各点開方であり、遅延フラグ

はできない.

long long貯留sum

他の人のブログを見ます:x意外にも>y

#include 
#include 
#include  
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:
",++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
",query(1,x,y));
			else update(1,x,y);
		}
		printf("
");
	}
	return 0;
}