随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

FZU 1608 Huge Mission

题目链接: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(
10, 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(10, n));
    }


    
return 0;
}

posted on 2011-04-03 00:05 英雄哪里出来 阅读(974) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理