个人的标准写法。
View Code 1 /* 2 线段树+修改区间+询问区间 3 */ 4 #include5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include
另一种写法。
View Code 1 /* 2 线段树 3 成段更新 4 */ 5 #include6 const int maxn = 100005; 7 int sum[ maxn<<2 ]; 8 int col[ maxn<<2 ]; 9 #define lson l,mid,rt<<110 #define rson mid+1,r,rt<<1|111 12 void PushUp( int rt ){13 sum[ rt ]=sum[ rt<<1 ]+sum[ rt<<1|1 ];14 return ;15 }16 void PushDown( int rt,int m ){17 if( col[ rt ] ){18 col[ rt<<1 ]=col[ rt<<1|1 ]=col[ rt ];19 sum[ rt<<1 ]=(m-m/2)*col[ rt ];20 sum[ rt<<1|1 ]=(m/2)*col[ rt ];21 col[ rt ]=0;22 }23 } 24 25 void build( int l,int r,int rt ){26 sum[ rt ]=1;27 col[ rt ]=0;28 if( l==r ){29 return ;30 }31 int mid;32 mid=(l+r)>>1;33 build( lson );34 build( rson );35 PushUp( rt );36 return ;37 }38 39 void update( int a,int b,int c,int l,int r,int rt ){40 if( a<=l && b>=r ){41 col[ rt ]=c;42 sum[ rt ]=(r-l+1)*c;43 return ;44 }45 PushDown( rt,r-l+1 );46 int mid;47 mid=(l+r)>>1;48 if( a<=mid ) update( a,b,c,lson );49 if( b>mid ) update( a,b,c,rson );50 PushUp( rt );51 return ;52 }53 /*54 int query( int a,int b,int l,int r,int rt ){55 if( a==l && b==r ){56 return sum[ rt ];57 }58 int mid;59 mid=(l+r)>>1;60 int t1,t2;61 if( b<=mid ) return query( a,b,lson );62 else if( a>mid ) return query( a,b,rson );63 else return query( a,mid,lson )+query( mid+1,b,rson );64 } 65 */66 int main(){67 int T;68 scanf("%d",&T);69 for(int i=1;i<=T;i++ ){70 int n;71 scanf("%d",&n);72 build( 1,n,1 );73 int t;74 scanf("%d",&t);75 int a,b,c;76 while( t-- ){77 scanf("%d%d%d",&a,&b,&c);78 update( a,b,c,1,n,1 );79 //for( int j=1;j<=25;j++ )printf("j:%d %d\n",j,sum[j]);80 }81 printf("Case %d: The total value of the hook is %d.\n",i,sum[ 1 ]/*query( 1,n,1,n,1 )*/ );82 }83 return 0;84 }