首页 > 代码库 > POJ 2777 && ZOJ 1610 &&HDU 1698 --线段树--区间更新
POJ 2777 && ZOJ 1610 &&HDU 1698 --线段树--区间更新
直接将这3题 放一起了 今天在做线段树的东西 这3个都是区间更新的 查询方式互相不同 反正都可以放到一起吧
直接先上链接了
touch me
touch me
touch me
关于涉及到区间的修改 -- 区间更新的话 分为 增减 或者 修改
主要就是个 laze 标记 就是延迟更新
对于区间更新的写法 一般是有2种 其一 仔细划分到每个细小的区间 另一 粗略划分
反正 ==我的代码里会给出2种写法 看自己喜好
hdu
1 //线段树 成段更新 ---> 替换 根结点的查询 2 3 #include <iostream> 4 using namespace std; 5 6 const int size = 100010; 7 8 struct data 9 {10 int l;11 int r;12 int flag;13 int sum;14 }tree[ size*3 ];15 16 void create( int root , int l , int r )17 {18 int mid = l + (r-l)/2;19 tree[root].l = l;20 tree[root].r = r;21 tree[root].flag = 0;22 if( l==r )23 {24 tree[root].sum = 1;25 return;26 }27 create( root<<1 , l , mid );28 create( root<<1|1 , mid+1 , r );29 tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;30 }31 32 void add( int root , int len )33 {34 tree[root<<1].flag = tree[root<<1|1].flag = tree[root].flag ;35 tree[root<<1].sum = ( len - len/2 ) * tree[root].flag ;36 tree[root<<1|1].sum = len/2*tree[root].flag;37 tree[root].flag = 0;38 }39 40 void update( int root , int L , int R , int num )41 {42 int mid = tree[root].l + ( tree[root].r - tree[root].l ) / 2;43 if( tree[root].l == L && tree[root].r==R )44 {45 tree[root].flag= num;46 tree[root].sum = num * ( tree[root].r - tree[root].l + 1 );47 return;48 }49 if( tree[root].flag )50 {51 add( root , tree[root].r-tree[root].l+1 );52 }53 if( R<=mid ) // 左子树 54 {55 update( root<<1 , L , R , num );56 }57 else if( L>=mid+1 ) // 右子树 58 {59 update( root<<1|1 , L , R , num );60 }61 else // 覆盖左右 子树 62 {63 update( root<<1 , L , mid , num );64 update( root<<1|1 , mid+1 , R , num );65 }66 tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; 67 }68 69 int main()70 {71 int t , n , oper;72 int L , R , num;73 while( ~scanf("%d",&t) )74 {75 for( int i = 1 ; i<=t ; i++ )76 {77 scanf( "%d",&n );78 scanf( "%d",&oper );79 create( 1 , 1 , n );80 while( oper-- )81 {82 scanf( "%d %d %d",&L,&R,&num );83 update( 1 , L , R , num );84 }85 printf( "Case %d: The total value of the hook is %d.\n",i,tree[1].sum );86 }87 }88 return 0;89 }
POJ
1 //线段树--区间更新--替换 区间查询---B 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 6 int sum; 7 const int size = 100010; 8 struct data 9 { 10 int l; 11 int r; 12 int color; 13 bool flag; 14 }tree[size*3]; 15 16 void create( int root , int l , int r ) 17 { 18 int mid = ( l + r ) / 2; 19 tree[root].l = l; 20 tree[root].r = r; 21 tree[root].color = 1; 22 tree[root].flag = false; 23 if( l==r ) 24 { 25 return; 26 } 27 create( root<<1 , l , mid ); 28 create( root<<1|1 , mid+1 , r ); 29 } 30 31 void add( int root ) 32 { 33 tree[root<<1].flag = true; 34 tree[root<<1|1].flag = true; 35 tree[root<<1].color = tree[root].color; 36 tree[root<<1|1].color = tree[root].color; 37 tree[root].flag = false; 38 } 39 40 void update( int root , int L , int R , int num ) 41 { 42 int mid = ( tree[root].l + tree[root].r ) / 2; 43 if( tree[root].l == L && tree[root].r ==R ) 44 { 45 tree[root].flag = true; 46 tree[root].color = num; 47 return; 48 } 49 if( tree[root].color == num ) 50 { 51 return; 52 } 53 if( tree[root].flag ) 54 { 55 add( root ); 56 } 57 if( L>=mid+1 ) 58 { 59 update( root<<1|1 , L , R , num ); 60 } 61 else if( R<=mid ) 62 { 63 update( root<<1 , L , R , num ); 64 } 65 else 66 { 67 update( root<<1 , L , mid , num ); 68 update( root<<1|1 , mid+1 , R , num ); 69 } 70 tree[root].color = tree[root<<1].color | tree[root<<1|1].color; 71 } 72 73 void query( int root , int L , int R ) 74 { 75 int mid = ( tree[root].l + tree[root].r ) / 2; 76 if( tree[root].l ==L && tree[root].r ==R ) 77 { 78 sum |= tree[root].color; 79 return; 80 } 81 if( tree[root].flag ) 82 { 83 add( root ); 84 } 85 if( L>=mid+1 ) 86 { 87 query( root<<1|1 , L , R ); 88 } 89 else if( R<=mid ) 90 { 91 query( root<<1 , L , R ); 92 } 93 else 94 { 95 query( root<<1 , L , mid ); 96 query( root<<1|1 , mid+1 , R ); 97 } 98 } 99 100 int main()101 {102 int cnt;103 int n , m , oper;104 char ch;105 int L , R , num;106 while( ~scanf("%d %d",&n,&m) )107 {108 create( 1 , 1 , n ); 109 scanf( "%d",&oper );110 while( oper-- )111 {112 getchar();113 scanf( "%c",&ch );114 if( ch==‘C‘ )115 {116 scanf( "%d %d %d",&L,&R,&num );117 if( L>R )118 {119 swap( L ,R );120 }121 update( 1 , L , R , 1<<(num-1) );122 } 123 else124 {125 scanf( "%d %d",&L,&R );126 if( L>R )127 {128 swap( L , R );129 }130 cnt = sum = 0;131 query( 1 , L , R );132 while( sum )133 {134 if( sum&1 )135 {136 cnt++;137 }138 sum>>=1;139 }140 printf( "%d\n",cnt );141 }142 } 143 }144 return 0;145 }
ZOJ
1 //线段树 --区间更新-替换 -- A 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 7 int n; 8 const int size = 8080; 9 struct data 10 { 11 int l; 12 int r; 13 int flag; 14 }tree[size*3]; 15 int color[size]; 16 int avoid; 17 int cnt[size]; 18 19 void create( int root , int l , int r ) 20 { 21 int mid = ( l + r ) / 2; 22 tree[root].l = l; 23 tree[root].r = r; 24 tree[root].flag = -1; 25 if( l==r ) 26 { 27 return; 28 } 29 create( root<<1 , l , mid ); 30 create( root<<1|1 , mid+1 , r ); 31 } 32 33 void add( int root ) 34 { 35 tree[root<<1].flag = tree[root<<1|1].flag = tree[root].flag; 36 tree[root].flag = -1; 37 } 38 39 void update( int root , int L , int R , int num ) 40 { 41 int mid = ( tree[root].l + tree[root].r )/2; 42 if( tree[root].flag == num ) 43 return; 44 if( tree[root].l>=L && tree[root].r<=R ) 45 { 46 tree[root].flag = num; 47 return; 48 } 49 if( tree[root].flag!=-1 ) 50 { 51 add( root ); 52 } 53 /* 54 if( R<=mid ) 55 { 56 update( root<<1 , L , R , num ); 57 } 58 else if( L>=mid+1 ) 59 { 60 update( root<<1|1 , L , R , num ); 61 } 62 else 63 { 64 update( root<<1 , L , mid , num ); 65 update( root<<1|1 , mid+1 , R , num ); 66 } 67 */ 68 if( L<=mid ) 69 { 70 update( root<<1 , L , R , num ); 71 } 72 if( R>mid ) 73 { 74 update( root<<1|1 , L , R , num ); 75 } 76 if( tree[root<<1].flag == tree[root<<1|1].flag && tree[root<<1].flag!=-1 ) 77 { 78 tree[root].flag = tree[root<<1].flag; 79 } 80 } 81 82 void solve( int root ) 83 { 84 if( tree[root].flag!=-1 ) 85 { 86 //cout<<"root"<<root<<endl; 87 for( int i = tree[root].l ; i<=tree[root].r ; i++ ) 88 { 89 color[i] = tree[root].flag; 90 //cout<<"color:"<<color[i]<<endl; 91 } 92 return; 93 } 94 if( tree[root].l == tree[root].r ) 95 return; 96 solve( root<<1 ); 97 solve( root<<1|1 ); 98 } 99 100 void getAns()101 {102 int former = -1;103 for( int i = 0 ; i<size ; i++ )104 {105 if( former != color[i] )106 {107 former = color[i];108 cnt[former]++;109 //cout<<"数量"<<cnt[former]<<" former:"<<former<<endl;110 }111 } 112 for( int i = 0 ; i<size ; i++ )113 {114 if( cnt[i]!=0 )115 {116 printf( "%d %d\n",i,cnt[i] );117 }118 }119 printf( "\n" );120 }121 122 int main()123 {124 int L , R , num;125 while( ~scanf("%d",&n) )126 {127 memset( color , -1 , sizeof(color) );128 memset( cnt , 0 , sizeof(cnt) );129 create(1,0,size);130 for( int i = 0 ; i<n ; i++ )131 {132 scanf( "%d %d %d",&L,&R,&num );133 update( 1 , L , R-1 , num );134 }135 solve(1);136 getAns();137 }138 return 0;139 }
today:
I am ingratiated by the sunset because of her sensitivity
As she tries to push the darkness back for just a moment more.
But like so many times before…To no avail!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。