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

[线段树成段更新]poj 2777

 
阅读更多

题意:

        一段区间从1-n的初始颜色为1,每次进行两种操作1,C a b c 把[a,b]这个区间染成颜色c。2,P a b查询[a,b]区间内有多少种颜色。

 

思路:

      这一题的关键在于用二进制存储一个区间内的颜色数量,新增颜色时对当前区间进行或操作来实现。

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

void update(int left ,int right ,int p ,int u){
//    cout<<left <<" tt "<<right<<" "<<u<<endl;
    if ( p == node[u].clo )return;
    if(left == node[u].l && right == node[u].r){
        node[u].clo = p;
        node[u].num = 1<<(p-1);
        return;
    }
    if(node[u].clo != 0){
        node[2*u].clo = node[u].clo;
        node[2*u].num = node[u].num;
        node[2*u+1].clo = node[u].clo;
        node[2*u+1].num = node[u].num;
        node[u].clo = 0;
        node[u].num = 0;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(left <= m){
        update(left , min(right , m), p ,u*2);
    }
    if(right >= m+1){
        update(max(left , m + 1) ,right ,p ,u*2+1);
    }
    node[u].num |= (node[2*u].num);
    node[u].num |= (node[2*u+1].num);
}
int ans;
void query(int left ,int right ,int u){
    if(node[u].clo != 0){
//            cout<<u<<" dddd "<<node[u].num<<" "<<node[u].clo<<endl;
        ans |= node[u].num;
        return;
    }
    int m = (node[u].l + node[u].r)>>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 gao(int a){
    int res = 0;
    while(a){
        if(a & 1)res++;
        a >>= 1;
    }
    return res;
}
int main(){
    int n ,k ,m ,i ,j , a, b ,c;
    char str[5];
    while( scanf("%d%d%d",&n,&k,&m)!=EOF){
        build(1 ,n ,1);
        while(m--){
            scanf("%s",str);
            if( str[0] == 'C'){
                scanf("%d%d%d",&a,&b,&c);
                update(a ,b ,c ,1);
            }else{
                scanf("%d%d",&a,&b);
                ans = 0;
                query(a ,b ,1);
//                cout<<ans<<endl;
                printf("%d\n",gao(ans));
            }
        }
    }
    return 0;
}

  

 

0
1
分享到:
评论

相关推荐

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

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

    《软件方法2024版》公开内容202405更新-epub版

    目前指正人有(按指正时间排序):吴佰钊、王周文、刘学斌、成文华、黄树成、李蜀斌、杨雪鸿、王书伟、高洪江、张志坚、龙燔、陈文飞、郭沼兵、陈自平、张彬、李宏伟、赵志军、孙赛刚、孙军、左科。 2018版《软件...

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

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

    商贸网站建设方案研讨.doc

    2020年4月19日的研讨文档提出了重庆树成通商贸的建设方案,旨在通过鼎维网络科技的专业服务,提升企业的信息化水平。 鼎维的独特优势在于其在网站/系统开发项目组的专业能力,能够提供定制化的解决方案,满足商贸...

    团队协作活动课程设计

    通过明确的分工,每个项目都有专门的负责人,如“动力火车”由魏珍负责,“盲人送水”由吴树成负责,“乒乓接力”由王薪凯负责,而梁誉川则负责其他物资,如粉笔、口哨和剪刀等。 总的来说,这个团队协作课程设计是...

    体育艺术节安全预案.docx

    - **成员**:姜国英、邓树成等 - **职责**:收集突发事件信息、调动人力、现场联络等。 - **治安维护组** - **组长**:陶红梅 - **成员**:郭本红、祝华等 - **职责**:维护校园秩序、巡查隐患、保障师生安全等...

    中国经济周期及波动浅析:1978-2005

    学者刘树成的研究认为,改革开放后,中国的经济周期呈现出波幅下降、波动高度降低、波动深度由负变正、波动位势上升以及扩张长度延长等显著特征。这些特征表明中国经济告别了以前“大起大落”的发展模式,进入了更为...

    oracle自动备份shell脚本

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

    2021精品手抄报系列-植树节小报27-A4.doc

    此外,植树标语还揭示了树木的多种益处,比如“树成荫”、“林成森”代表了森林对气候的调节作用,“抵御外敌”和“造福人类”强调了森林对于生态平衡的重要性,“人养树,树养人”则表达了人与自然和谐共生的理念。...

    利率自由化与中国银行业的改革和发展.docx

    在模型分析中,如刘树成等人的研究,利率自由化会直接影响银行的收益,优化银行的决策行为。降低不良贷款比率和提高银行效率有助于提高银行收益。利率市场化初期,可能会给银行带来压力,但随着市场化进程的推进,...

    吉林省经济发展现状.pdf

    文献中,刘树成等人探讨了经济周期波动平滑化,强调稳定增长和轻微波动的经济状态。孙晓祥则指出吉林经济发展虽总体向好,但与全国平均水平相比仍有差距,产业结构不合理,尤其是第一产业比重偏高,第三产业滞后。杨...

    学校消防安全每日防火巡查制度—【安全资料】..doc

    防火巡查人员包括李树成、张欢欢、周玉彬、冯丞丞、陈建文、彭勇、李先勇、李华军、杨小灵等,他们在日常工作中负责执行防火巡查任务,对校园内的消防安全情况进行全面监督和检查。 二、巡查部位与频次 巡查应覆盖...

    校消防安全每日防火巡查制度与校消防安全管理制度(一).pdf

    1. **巡查人员**:指定特定人员如李树成等人进行每日防火巡查,确保责任落实。 2. **巡查频次**:公众聚集场所需至少每日一次巡查,必要时增加次数,并记录于台帐。夜间巡查视具体情况强化。 3. **巡查内容**:包括...

    二年级语文上册 10.北京同步练习 新人教版-新人教版小学二年级上册语文试题.doc

    - 在第二课时的成语填充中,例如“( )树成阴”(绿树成阴)、“鲜( )盛( )”(鲜花盛开)、“风( )( )景”(风景优美)、“( )流( )息”(川流不息)、“( )( )往往”(来来往往)、“( )楼( ...

    光照鲁棒的人脸识别.pdf

    这篇由任树成、周激流、何坤和夏建平等人发表在《激光杂志》2009年30卷5期的文章探讨了如何克服光照变化对人脸识别的影响。 传统的人脸识别方法通常分为两类:一种是基于几何特征的方法,这类方法通过分析面部特征...

    成品保护措施(成稿).doc

    在【施工部署】中,项目成立了由田树成担任组长的成品保护领导小组,成员包括单文林、付万河等,他们负责检查和监督现场各分包商的成品和半成品保护情况,并采取相应的保护措施。这样的组织结构确保了保护措施的有效...

    基于新能源的装备电池模块设计探讨.pdf

    论文作者李树成在文中主要探讨了基于新能源的装备电池模块的构成、常见类型以及设计思路。 1. **电池构成与常见类型** - **铅酸蓄电池**:尽管不是新型电池,但由于成本低,仍被广泛应用。 - **锂电池**:因其高...

    幼儿园老师工会活动方案.pdf

    拓展训练的组织工作同样非常严谨,我们明确了总指挥和副指挥的人选,包括杨晓红、武秀玲、丁荣秋、张玉妹、曹连英、树成霞等六位,以及负责联络的张蓉、杨雪玲、陈凤珍、江晶晶四位老师。此外,我们还对参与者的着装...

    语言活动《过生日》.doc

    随着故事的深入,孩子们会发现,在乖乖生日时,所有的朋友都来为他送上礼物,一棵挂满了礼物的树成了对乖乖乐于助人品质的最好回报。孩子们在感动于故事的同时,也开始认识到真诚待人的重要性,从而学会尊重和珍视...

Global site tag (gtag.js) - Google Analytics