|
|
題目鏈接：http://acm.fzu.edu.cn/problem.php?pid=1608
  /**//*
題意：
給定M個區(qū)間 (1 <= M <= 500000)和這些區(qū)間上的權(quán)值，求最終并區(qū)間的最
大權(quán)值總和（某個區(qū)間不能被計算兩次）。
解法：
線段樹
思路：
因為最后詢問只有一次，而多次的插入操作，所以這個問題有個很簡單的解
決辦法，每次更新的時候只更新到區(qū)間完全覆蓋的情況，這樣的復(fù)雜度是log(n)
的，而最后詢問的時候來一次O(nlogn)的操作，一直查詢到元區(qū)間，每次將當(dāng)前
區(qū)間的最大值向下傳遞給兩個兒子。統(tǒng)計時只要統(tǒng)計元區(qū)間的最值和即可。
 */
#include <iostream>
using namespace std;
#define maxn 50010
struct Tree  {
int Max;
int root, l, r;
void CoverBy(int lazy);
  int len() {
return r - l;
 }
}T[maxn*4];
int n, m;
void Build(int root, int l, int r) {
T[root].root = root;
T[root].l = l;
T[root].r = r;
T[root].Max = 0;
if(l + 1 == r || l == r) {
return ;
}
int mid = (l + r) >> 1;
Build(root<<1, l, mid);
Build(root<<1|1, mid, r);
}
void Tree::CoverBy(int lazy) {
if(lazy > Max) {
Max = lazy;
}
}
void Insert(int root, int l, int r, int val) {
if(l >= T[root].r || r <= T[root].l) {
return ;
}
if(l <= T[root].l && T[root].r <= r) {
T[root].CoverBy(val);
return ;
}
Insert(root<<1, l, r, val);
Insert(root<<1|1, l, r, val);
}
int Query(int root, int l, int r) {
if(l + 1 == r) {
return T[root].Max;
}
T[root<<1].CoverBy(T[root].Max);
T[root<<1|1].CoverBy(T[root].Max);
int mid = (l + r) >> 1;
return Query(root<<1, l, mid) + Query(root<<1|1, mid, r);
}
int main() {
int i;
while(scanf("%d %d", &n, &m) != EOF) {
Build(1, 0, n);
for(i = 0; i < m; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
Insert(1, x, y, z);
}
printf("%d\n", Query(1, 0, n));
}
return 0;
}
|