首页 > 代码库 > 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