首页 > 代码库 > 线段树 区间更新
线段树 区间更新
poj3468 A Simple Problem with Integers
( m - ( m >> 1 ) )这里跪了几发。。 - 的优先级大于 >>
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 10400013 #define ll long long14 #define mod 100000000715 #define inf 0x3f3f3f3f16 #define lson l, m, rt << 117 #define rson m+1, r, rt << 1 | 118 19 ll sum[mnx<<2], col[mnx<<2];20 int n;21 void pushup( int rt ){22 sum[rt] = sum[rt<<1] + sum[rt<<1|1];23 }24 void pushdown( int rt, int m ){25 if( col[rt] ){26 col[rt<<1] += col[rt];27 col[rt<<1|1] += col[rt];28 sum[rt<<1|1] += ( m >> 1 ) * col[rt] ;29 sum[rt<<1] += ( m - ( m >> 1 ) ) * col[rt] ;30 col[rt] = 0;31 }32 }33 void build( int l, int r, int rt ){34 col[rt] = 0;35 if( l == r ){36 scanf( "%I64d", &sum[rt] );37 return;38 }39 int m = ( l + r ) >> 1;40 build( lson );41 build( rson );42 pushup( rt );43 }44 void update( int L, int R, int v, int l, int r, int rt ){45 if( L <= l && R >= r ){46 sum[rt] += ( r - l + 1 ) * (ll)v;47 col[rt] += v;48 return ;49 }50 pushdown( rt, r - l + 1 );51 int m = ( l + r ) >> 1;52 if( L <= m ) update( L, R, v, lson );53 if( R > m ) update( L, R, v, rson );54 pushup( rt );55 }56 ll find( int L, int R, int l, int r, int rt ){57 ll ret = 0;58 if( L <= l && R >= r ){59 return sum[rt];60 }61 pushdown( rt, r - l + 1 );62 int m = ( l + r ) >> 1;63 if( L <= m ) ret += find( L, R, lson );64 if( R > m ) ret += find( L, R, rson );65 //pushup( rt );66 return ret;67 }68 int main(){69 int q;70 while( scanf( "%d %d", &n, &q ) != EOF ){71 build( 1, n, 1 );72 getchar();73 while( q-- ){74 char c;75 int a, b, v;76 cin >> c;77 if( c == ‘Q‘ ){78 scanf( "%d %d", &a, &b );79 printf( "%I64d\n", find( a, b, 1, n, 1 ) );80 }81 else{82 scanf( "%d %d %d", &a, &b, &v );83 update( a, b, v, 1, n, 1 );84 }85 }86 }87 return 0;88 }
poj2528 Mayor’s posters
题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了[1,4][1,2][3,4]
线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了。。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 1001013 #define ll long long14 #define mod 100000000715 #define inf 0x3f3f3f3f16 #define lson l, m, rt << 117 #define rson m+1, r, rt << 1 | 118 19 int lx[mnx], rx[mnx], sum[mnx<<2], col[mnx<<4], n, ans;20 bool vis[mnx<<2];21 void pushdown( int rt ){22 if( col[rt] ){23 col[rt<<1] = col[rt<<1|1] = col[rt];24 col[rt] = 0;25 }26 }27 void update( int L, int R, int v, int l, int r, int rt ){28 if( L <= l && R >= r ){29 col[rt] = v;30 return ;31 }32 pushdown( rt );33 int m = ( l + r ) >> 1;34 if( L <= m ) update( L, R, v, lson );35 if( R > m ) update( L, R, v, rson );36 }37 38 int bin_search( int goal, int n ){39 int l = 0, r = n - 1;40 while( l < r ){41 int m = ( l + r ) >> 1;42 if( sum[m] < goal ){43 l = m + 1;44 }45 else r = m;46 }47 return l;48 }49 void find( int l, int r, int rt ){50 if( l == r ){51 if( col[rt] == 0 ) return ;52 if( !vis[col[rt]] ) ans++;53 vis[col[rt]] = 1;54 return ;55 }56 pushdown( rt );57 int m = ( l + r ) >> 1;58 find( lson );59 find( rson );60 }61 int main(){62 int cas;63 scanf( "%d", &cas );64 while( cas-- ){65 memset( col, 0, sizeof(col) );66 memset( vis, 0, sizeof(vis) );67 int cnt = 0;68 scanf( "%d", &n );69 for( int i = 0; i < n; i++ ){70 scanf( "%d %d", &lx[i], &rx[i] );71 sum[cnt++] = lx[i];72 sum[cnt++] = rx[i];73 }74 sort( sum, sum + cnt );75 cnt = unique( sum, sum + cnt ) - sum;76 int kk = cnt;77 for( int i = 1; i < cnt; i++ ){78 if( sum[i] - sum[i-1] != 1 ){79 sum[kk++] = sum[i-1] + 1;80 }81 }82 sort( sum, sum + kk );83 for( int i = 0; i < n; i++ ){84 int l = bin_search( lx[i], kk ) + 1;85 int r = bin_search( rx[i], kk ) + 1;86 //cout<<l<<" "<<r<<endl;87 update( l, r, i+1, 1, kk, 1 );88 }89 ans = 0;90 find( 1, kk, 1 );91 printf( "%d\n", ans );92 }93 return 0;94 }
poj3225 Help with Intervals
做的好恶心啊，只好边看代码边做。。
题意:区间操作,交,并,补等
思路:
我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含)
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作
很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了
所以当一个节点得到覆盖标记时把异或标记清空
而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记
开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间)
线段树功能:update:成段替换,区间异或 query:简单hash
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std; 11 12 #define mnx 131072 13 #define ll long long 14 #define mod 1000000007 15 #define inf 0x3f3f3f3f 16 #define lson l, m, rt << 1 17 #define rson m+1, r, rt << 1 | 1 18 19 const int n = 131072; 20 int cover[mnx<<2], Xor[mnx<<2]; 21 bool vis[mnx+1]; 22 void Fxor( int rt ){ 23 if( cover[rt] != -1 ) cover[rt] ^= 1; 24 else Xor[rt] ^= 1; 25 } 26 void pushdown( int rt ){ 27 if( cover[rt] != -1 ){ 28 cover[rt<<1] = cover[rt<<1|1] = cover[rt]; 29 Xor[rt<<1] = Xor[rt<<1|1] = 0; 30 cover[rt] = -1; 31 } 32 if( Xor[rt] ){ 33 Fxor( rt<<1 ); 34 Fxor( rt<<1|1 ); 35 Xor[rt] = 0; 36 } 37 } 38 void update( int L, int R, char c, int l, int r, int rt ){ 39 if( L <= l && R >= r ){ 40 if( c == ‘U‘ ){ 41 cover[rt] = 1; 42 Xor[rt] = 0; 43 } 44 else if( c == ‘D‘ ){ 45 cover[rt] = 0; 46 Xor[rt] = 0; 47 } 48 else if( c == ‘S‘ || c == ‘C‘ ){ 49 Fxor( rt ); 50 } 51 return ; 52 } 53 pushdown( rt ); 54 int m = ( l + r ) >> 1; 55 if( L <= m ) update( L, R, c, lson ); 56 else if( c == ‘C‘ || c == ‘I‘ ){ 57 cover[rt<<1] = Xor[rt<<1] = 0; 58 } 59 if( R > m ) update( L, R, c, rson ); 60 else if( c == ‘C‘ || c == ‘I‘ ){ 61 cover[rt<<1|1] = Xor[rt<<1|1] = 0; 62 } 63 } 64 void find( int l, int r, int rt ){ 65 if( cover[rt] == 1 ){ 66 for( int i = l; i <= r; i++ ){ 67 vis[i] = 1; 68 } 69 return ; 70 } 71 if( cover[rt] == 0 ) return; 72 pushdown( rt ); 73 int m = ( l + r ) >> 1; 74 find( lson ); 75 find( rson ); 76 } 77 int main(){ 78 char op, a, b; 79 int l, r; 80 while( scanf( "%c %c%d,%d%c\n", &op, &a, &l, &r, &b ) != EOF ){ 81 l <<= 1, r <<= 1; 82 if( a == ‘(‘ ) l++; 83 if( b == ‘)‘ ) r--; 84 if( l > r ){ 85 if( op == ‘C‘ || op == ‘I‘ ){ 86 cover[1] = Xor[1] = 0; 87 } 88 } 89 else update( l, r, op, 0, n, 1 ); 90 } 91 find( 0, n, 1 ); 92 l = -1; 93 bool flag = 0; 94 for( int i = 0; i < n; i++ ){ 95 if( vis[i] ){ 96 if( l == -1 ){ 97 l = i; 98 } 99 r = i;100 }101 else{102 if( l == -1 ) continue;103 if( flag ) printf( " " );104 flag = 1;105 printf( "%c%d,%d%c", l&1 ? ‘(‘ : ‘[‘, l>>1, (r+1)>>1, r&1 ? ‘)‘ : ‘]‘ );106 l = -1;107 }108 }109 if( !flag ) printf( "empty set" );110 printf( "\n" );111 return 0;112 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。