HDU1698+线段树

个人的标准写法。

View Code
  1 /*
  2 线段树+修改区间+询问区间
  3 */
  4 #include<stdio.h>
  5 #include<string.h>
  6 #include<stdlib.h>
  7 #include<algorithm>
  8 #include<iostream>
  9 #include<queue>
 10 #include<vector>
 11 #include<map>
 12 #include<math.h>
 13 typedef long long ll;
 14 //typedef __int64 int64;
 15 const int maxn = 100005;
 16 const int maxm = 1005;
 17 const int inf = 0x7FFFFFFF;
 18 const double pi = acos(-1.0);
 19 const double eps = 1e-8;
 20 using namespace std;
 21 #define LEFT( x ) (x<<1)
 22 #define RIGHT( x ) ((x<<1)+1)
 23 struct node{
 24     int l,r,sum;
 25     int flag;
 26 }tree[ maxn<<2 ];
 27 int data[ maxn ];
 28 void pushup( int n ){
 29     tree[ n ].sum = tree[ LEFT( n ) ].sum+tree[ RIGHT( n ) ].sum;
 30     return ;
 31 }
 32 void pushdown( int n,int m ){//下标为n,这段区间有m个数
 33     if( tree[ n ].flag!=0 ){
 34         tree[ LEFT( n ) ].flag = tree[ RIGHT( n ) ].flag = tree[ n ].flag;
 35         tree[ LEFT( n ) ].sum =  tree[ n ].flag*(m-m/2);//tree[ n ].flag*((m+1)/2);
 36         tree[ RIGHT( n ) ].sum = tree[ n ].flag*(m/2);//tree[ n ].flag*( m-(m+1)/2 );
 37         tree[ n ].flag = 0;
 38     }
 39     return;
 40 }
 41 void build( int l,int r,int n ){
 42     if( l==r ){
 43         tree[ n ].sum = data[ l ];
 44         tree[ n ].flag = 0;
 45         tree[ n ].l=tree[ n ].r = l;
 46         return ;
 47     }
 48     tree[ n ].flag = 0;
 49     tree[ n ].l = l;
 50     tree[ n ].r = r;
 51     int mid;
 52     mid = (l+r)>>1;
 53     build( l,mid,LEFT( n ) );
 54     build( mid+1,r,RIGHT( n ) );
 55     pushup( n );
 56     return;
 57 }
 58 void update( int a,int b,int c,int l,int r,int n ){
 59     if( a==l&&b==r ){
 60         tree[ n ].flag = c;
 61         tree[ n ].sum = (r-l+1)*c;
 62         return ;
 63     }
 64     pushdown( n,r-l+1 );
 65     //printf("test\n");
 66     int mid;
 67     mid = (l+r)>>1;
 68     if( mid>=b ) update( a,b,c,l,mid,LEFT( n ) );
 69     else if( mid<a ) update( a,b,c,mid+1,r,RIGHT( n ));
 70     else {
 71         update( a,mid,c,l,mid,LEFT( n ) );
 72         update( mid+1,b,c,mid+1,r,RIGHT( n ) );
 73     }
 74     pushup( n );
 75     return ;
 76 }
 77 int query( int a,int b,int l,int r,int n ){
 78     if( a==l&&b==r ){
 79         return tree[ n ].sum;
 80     }
 81     pushdown( n,r-l+1 );
 82     int mid;
 83     mid = (l+r)>>1;
 84     if( mid>=b ) return query( a,b,l,mid,LEFT( n ) );
 85     else if( mid<a ) return query( a,b,mid+1,r,RIGHT( n ));
 86     else return query( a,mid,l,mid,LEFT( n ) )+query( mid+1,b,mid+1,r,RIGHT( n ));
 87 }
 88 int main(){
 89     int ca;
 90     scanf("%d",&ca);
 91     for( int t=1;t<=ca;t++ ){
 92         int n;
 93         scanf("%d",&n);
 94         for( int i=1;i<=n;i++ ){
 95             data[ i ] = 1;
 96         }
 97         build( 1,n,1 );
 98         int op;
 99         scanf("%d",&op);
100         while( op-- ){
101             int a,b,c;
102             scanf("%d%d%d",&a,&b,&c);
103             update( a,b,c,1,n,1 );
104         }
105         printf("Case %d: The total value of the hook is %d.\n",t,tree[ 1 ].sum);
106     }
107     return 0;
108 }

 另一种写法。

View Code
 1 /*
 2 线段树
 3 成段更新
 4 */
 5 #include<stdio.h>
 6 const int maxn = 100005;
 7 int sum[ maxn<<2 ];
 8 int col[ maxn<<2 ];
 9 #define lson l,mid,rt<<1
10 #define rson mid+1,r,rt<<1|1
11 
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 }
keep moving...
原文地址:https://www.cnblogs.com/xxx0624/p/3023055.html