HDU-1698-Just a Hook(線分樹-セグメント更新)

2018 ワード

HDU ~データ構造 BIT &&& RMQ 線分樹

テーマ転送: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.
", cas, sum[1]);
	}
	return 0;
}

R言語-データボックス