题意:
一段区间从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; }
相关推荐
作者:Persegrand.Spiniper(树成) 编写时间:2008年8月10日 版本:1.1 该控件以发现且未解决缺陷: 1、点击下拉单的滚动条然后失去焦点不会使下拉单消失。 2、显示长度过长会出现换行现象,没有进行字符串截取...
总结了一套科学的方法。如果自己一个人,或者团队人数也有限,只能主做商业领域,剩下财经、体育、母婴、旅游、情感、健康、职场......等等一系列行业,都没法做,我既没时间,也不可能懂这么多行业的专业知识。...
选煤厂浮选尾煤资源化利用技术浅析,柳树成,盛啸,煤炭工业的快速发展以及煤炭入选量的急剧增大,使得尾煤产生量越来越大。合理开发尾煤资源对缓解我国能源危机以及控制因尾煤带来
方形软包锂离子电池热物性参数的辨识方法,陈树成,吕超,锂离子电池具有高能量密度和长循环寿命等优点,使其在不同应用场合都得到了广泛的关注,其热相关问题关系到电池性能、寿命、安全
特别说明:此shell代码为原创,放在csdn上供大家下载,如果大家喜欢此代码,或者觉得值得推荐给他人,在其他网站或者地址提供下载,本人表示欢迎,只是希望各位注明出处,提供者为——树成,源地址为...
... 本脚本通过rhel5.x安装oracle10g与oracle11g的测试无误,其它linux版本不保证能正常工作。 此脚本使用方法: ... 运行简介: ...service oraclectrl start --启动数据库与侦听 service oraclectrl start db --仅仅启动...