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