程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU4027 Can you answer these queries 線段樹區間求和+剪枝

HDU4027 Can you answer these queries 線段樹區間求和+剪枝

編輯：C++入門知識

給了你n，然後n個數字在一個數組中，接下來m個詢問，每個詢問三個數字 t,x,y,若t==0，那麼修改區間[x,y]的每一個值，變為原來每個位置上的數開根號取整，若t==1，那麼對區間[x,y]求和

由於n,m,很大，所以樹狀數組鐵定超時，若直接用線段樹來做區間修改，那麼也是超時，這類題目沒別的方法了，靜心剪枝，發現題目給的數據范圍為2^63,有沒有發現，2^63開根號絕對不需要開10次，就能到1，到1以後就不需要再開了，意思就是若有某個區間[x,y]每一個點的值都為1時，這一段區間事實上是不需要處理的，怎麼判斷呢，簡單，這個區間的和等於區間大小就是了，

都改好了也不TLE了，也不WA了，但是一直RE，搞不懂，直到最後也沒搞懂，最後有隊友說題目給的區間 [x,y], x的值不一定比y小，所以需要判別一下，題目在交代x,y的取值范圍時，確實沒有說x

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

const int N = 100000 + 5;

typedef struct Node {
	int l,r;
	LL sum;
};

Node tree[N * 4];

LL a[N];

int n;

void build_tree(int left,int right,int id) {
	tree[id].l = left;
	tree[id].r = right;
	tree[id].sum = 0;
	if(left == right) {
		tree[id].sum = a[left];
		return;
	}
	int mid = (left + right)>>1;
	build_tree(left,mid,id * 2);
	build_tree(mid+1,right,id * 2 + 1);
	tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
}

void update(int left,int right,int id) {
	if(tree[id].l == left && tree[id].r == right) {
		if(tree[id].sum ==right - left + 1) return;//區間和等於區間長度沒必要更新處理
		else if(left == right) {
			tree[id].sum = sqrt(tree[id].sum * 1.0);
			return ;
		}
	}
	LL mid = (tree[id].l + tree[id].r)>>1;
	if(right <= mid) 
		update(left,right,id * 2);
	else  if(left > mid)
		update(left,right,id * 2 + 1);
	else {
		update(left,mid,id * 2);
		update(mid + 1,right,id * 2 + 1);
	}
	tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
}

LL query(int left,int right,int id) {
	if(tree[id].l == left && tree[id].r == right) return tree[id].sum;
	int mid = (tree[id].l + tree[id].r)>>1;
	if(right <= mid)
		return query(left,right,id * 2);
	else if(left > mid) 
		return query(left,right,id * 2 + 1);
	else
		return query(left,mid,id * 2) + query(mid + 1,right,id * 2 + 1);
}

int main() {
	int	Case = 0;
	while(scanf("%d",&n) == 1) {
		for(int i=1;i<=n;i++)
			scanf("%I64d",&a[i]);
		build_tree(1,n,1);
		int m;
		scanf("%d",&m);
		int t,x,y;
		printf("Case #%d:\n",++Case);
		while(m--) {
			scanf("%d %d %d",&t,&x,&y);
			if(x > y)
				swap(x,y);
			if(t == 0) {
				update(x,y,1);
			}
			else {
				printf("%I64d\n",query(x,y,1));
			}
		}
		puts("");
	}
	return 0;
}