`
暴风雪
  • 浏览: 375031 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[线段树成段更新]hdoj 1698

 
阅读更多

题意:

    对一个线段上的值进行修改,一次可以把[i,j]这个区间上的值改为1,2,或3。1---n这个区间上数字的和

 

思路:

     一道很加深对成段更新理解的题目,需要成段更新加上一点技巧具体见代码update()

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100010;
struct{
    int l, r, sum, lazy;
}node[3 * nMax];
int ans;
void build(int l ,int r ,int u){
    node[u].l = l;
    node[u].r = r;
    node[u].lazy = 1;
    if(l == r){
        node[u].sum = 1;
        return ;
    }
    int m = (l + r)>>1;
    build(l ,m ,u * 2);
    build(m+1 , r , u*2+1);
}

//lazy值为0的时候代表这个区间上数字不唯一,初始值为1
void update(int left ,int right , int val ,int u){
    if(node[u].lazy == val)return;
    if(left == node[u].l && right == node[u].r){
        node[u].lazy = val;
        return;
    }
    if(node[u].lazy != 0){
        //当需要更新的线段数字唯一时,把这个lazy标记放到下面的节点上
        node[2*u].lazy = node[2*u+1].lazy = node[u].lazy;
        node[u].lazy = 0;
    }
    int m = (node[u].r + node[u].l)>>1;
    if(left <= m){
        update(left , min(right ,node[u*2].r), val, u*2);
    }
    if(right >= m+1){
        update(max(left ,m+1) , right , val, u*2 + 1);
    }
}
void query(int left ,int right ,int u){
    int l = node[u].l;
    int r = node[u].r;
    int w = right - left + 1;
    if(node[u].lazy != 0){
        ans += w*node[u].lazy;
        return;
    }
    int m = (r + l)>>1;
    if(right <= m){
        query(left , right , u*2);
        return;
    }
    if(left >= m+1){
        query(left , right , u*2+1);
        return;
    }
    query(left , m , u*2);
    query(m+1 , right , u*2 + 1);
}
int main(){
    int tcs,tt,n,m,a,b,c;
    scanf("%d",&tcs);
    for(tt = 1 ; tt <= tcs ; tt++){
        scanf("%d",&n);
        build(1 ,n ,1);
        scanf("%d",&m);
        while(m --){
            scanf("%d%d%d",&a,&b,&c);
            update(a ,b ,c ,1);
        }
        ans=0;
        query(1 , n ,1);
        printf("Case %d: The total value of the hook is %d.\n",tt,ans);
//        printf("%d\n",ans);
    }
    return 0;
}

 

 

0
0
分享到:
评论

相关推荐

    js可编辑下拉菜单——树成原创

    作者:Persegrand.Spiniper(树成) 编写时间:2008年8月10日 版本:1.1 该控件以发现且未解决缺陷: 1、点击下拉单的滚动条然后失去焦点不会使下拉单消失。 2、显示长度过长会出现换行现象,没有进行字符串截取...

    自媒体IP训练营课程-视频教程网盘链接提取码下载 .txt

    总结了一套科学的方法。如果自己一个人,或者团队人数也有限,只能主做商业领域,剩下财经、体育、母婴、旅游、情感、健康、职场......等等一系列行业,都没法做,我既没时间,也不可能懂这么多行业的专业知识。...

    选煤厂浮选尾煤资源化利用技术浅析

    选煤厂浮选尾煤资源化利用技术浅析,柳树成,盛啸,煤炭工业的快速发展以及煤炭入选量的急剧增大,使得尾煤产生量越来越大。合理开发尾煤资源对缓解我国能源危机以及控制因尾煤带来

    方形软包锂离子电池热物性参数的辨识方法

    方形软包锂离子电池热物性参数的辨识方法,陈树成,吕超,锂离子电池具有高能量密度和长循环寿命等优点,使其在不同应用场合都得到了广泛的关注,其热相关问题关系到电池性能、寿命、安全

    oracle自动备份shell脚本

    特别说明:此shell代码为原创,放在csdn上供大家下载,如果大家喜欢此代码,或者觉得值得推荐给他人,在其他网站或者地址提供下载,本人表示欢迎,只是希望各位注明出处,提供者为——树成,源地址为...

    oracle启动与管理服务脚本

    ... 本脚本通过rhel5.x安装oracle10g与oracle11g的测试无误,其它linux版本不保证能正常工作。 此脚本使用方法: ... 运行简介: ...service oraclectrl start --启动数据库与侦听 service oraclectrl start db --仅仅启动...

Global site tag (gtag.js) - Google Analytics