程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU - 1698 - Just a Hook （線段樹-成段更新）

HDU - 1698 - Just a Hook （線段樹-成段更新）

編輯：C++入門知識

HDU - 1698 - Just a Hook （線段樹-成段更新）

題目傳送：Just a Hook

思路：線段樹，成段替換，區間求和。成段更新時，注意延遲標記的作用，它就是用來暫停往下更新來達到節省時間的，然後每次更新每個節點的子節點之前都要判斷是否需要往下更新。

AC代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 100005;

int sum[maxn << 2];//求區間和 
int lazy[maxn << 2];//延遲標記 

void pushdown(int rt, int m) {
	if(lazy[rt]) {//如果之前這裡做了標記，則說明沒有往下更新，暫停了一下，用來判斷是否需要往下更新 
		lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
		sum[rt << 1] = (m - (m >> 1)) * lazy[rt];
		sum[rt << 1 | 1] = (m >> 1) * lazy[rt];
		lazy[rt] = 0;//往下更新完後，標記置為0，即當前不需要往下更新 
	}
}

void build(int l, int r, int rt) {
	lazy[rt] = 0;
	sum[rt] = r - l + 1;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
}

void update(int L, int R, int c, int l, int r, int rt) {
	if(L <= l && r <= R) {
		sum[rt] = c * (r - l + 1);
		lazy[rt] = c;//延遲標記，每次把該段更新完後暫時不往下更新，節省時間 
		return;
	}
	pushdown(rt, r - l + 1);//向下更新 
	int mid = (l + r) >> 1;
	if(L <= mid) update(L, R, c, l, mid, rt << 1);
	if(R >= mid + 1) update(L, R, c, mid + 1, r, rt << 1 | 1);
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];//向上更新 
}

int main() {
	int T, n, m;
	scanf("%d", &T);
	for(int cas = 1; cas <= T; cas ++) {
		scanf("%d %d", &n, &m);
		build(1, n, 1);
		
		for(int i = 0; i < m; i ++) {
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			update(a, b, c, 1, n, 1);
		}
		
		printf("Case %d: The total value of the hook is %d.\n", cas, sum[1]);
	}
	return 0;
}