|
|
题目链接：http://acm.fzu.edu.cn/problem.php?pid=1608
  /**//*
题意：
给定M个区间 (1 <= M <= 500000)和这些区间上的权值，求最终并区间的最
大权值总和（某个区间不能被计算两次）。
解法：
线段树
思路：
因为最后询问只有一次，而多次的插入操作，所以这个问题有个很简单的解
决办法，每次更新的时候只更新到区间完全覆盖的情况，这样的复杂度是log(n)
的，而最后询问的时候来一次O(nlogn)的操作，一直查询到元区间，每次将当前
区间的最大值向下传递给两个儿子。统计时只要统计元区间的最值和即可。
 */
#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;
}
|