首页 > 代码库 > HDU 1698
HDU 1698
成段更新
这是一种把 num[]上空结点当做lazy标志使用的方法
都一样。。。
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 #define lson l,mid,id<<1 8 #define rson mid+1,r,id<<1|1 9 const int MM=100002;10 int num[MM<<2];11 int flag;12 void down(int k)13 {14 num[k<<1]=num[k<<1|1]=num[k];15 num[k]=0;16 }17 void buildtree(int l,int r,int id)18 {19 num[id]=flag;20 if(l==r)21 {22 return;23 }24 else25 {26 int mid=(l+r)>>1;27 buildtree(l,mid,id<<1);28 buildtree(mid+1,r,id<<1|1);29 }30 }31 int query(int l,int r,int id)32 { 33 if(num[id])34 {35 return (r-l+1)*num[id];36 37 }int mid=(l+r)>>1,t1,t2;38 t1=query(lson);39 t2=query(rson);40 return t1+t2; 41 }42 void update(int L,int R,int l,int r,int id)43 {44 if(L<=l&&r<=R)45 {46 num[id]=flag;return;47 }48 if(num[id])down(id);49 int mid=(l+r)>>1;50 if(L<=mid)update(L,R,lson);51 if(R>mid)update(L,R,rson);52 }53 int main()54 {55 int t,n,m,cas,i,x,y,ans;56 scanf("%d",&t);57 for(cas=1;cas<=t;cas++)58 {59 scanf("%d %d",&n,&m);60 flag=1;61 buildtree(1,n,1);62 while(m--)63 {64 scanf("%d %d %d",&x,&y,&flag);65 update(x,y,1,n,1);66 }67 ans=query(1,n,1);68 printf("Case %d: The total value of the hook is %d.\n",cas,ans );69 }70 return 0;71 }
HDU 1698
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。