线段树 区间更新
分类:
IT文章
•
2024-01-07 13:49:36
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 104000
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 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
", 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 }
View Code
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 10010
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 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
", ans );
92 }
93 return 0;
94 }
View Code
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
", &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( "
" );
111 return 0;
112 }
View Code
poj1436 Horizontally Visible Segments
题目大意是,给出了很多条平行于y轴的线段,然后定义,两条线段能互相‘看见’的条件是,两条线段能由一条水平线连接,且这条水平线不能跟其他的所有线段有交点。
而题目要求的是,3个线段能互相看见,这个条件下有多少组不同的。
线段树区间覆盖,先按照x的坐标排序,然后每次覆盖前询问。。还有就是区间[1, 2] [3, 4]没有把区间[1,4]全部覆盖,所以线段树要开2倍,把输入的区间做乘2处理
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 8005
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 = mnx<<1;
20 int cover[mnx<<3], used[mnx], n;
21 struct seg{
22 int l, r, x;
23 bool operator < ( const seg & b ) const{
24 return x < b.x;
25 }
26 }p[mnx];
27 vector<int> g[mnx];
28 void init(){
29 memset( used, 0, sizeof(used) );
30 memset( cover, 0, sizeof(cover) );
31 }
32 void pushdown( int rt ){
33 if( cover[rt] ){
34 cover[rt<<1] = cover[rt<<1|1] = cover[rt];
35 cover[rt] = 0;
36 }
37 }
38 void update( int L, int R, int v, int l, int r, int rt ){
39 if( L <= l && R >= r ){
40 cover[rt] = v;
41 return ;
42 }
43 pushdown( rt );
44 int m = ( l + r ) >> 1;
45 if( L <= m ) update( L, R, v, lson );
46 if( R > m ) update( L, R, v, rson );
47 }
48 void query( int L, int R, int v, int l, int r, int rt ){
49 if( L <= l && R >= r ){
50 if( cover[rt] ){
51 if( used[cover[rt]] != v ){
52 used[cover[rt]] = v;
53 g[cover[rt]].push_back( v );
54 }
55 return ;
56 }
57 }
58 if( l == r ) return ;
59 pushdown( rt );
60 int m = ( l + r ) >> 1;
61 if( L <= m ) query( L, R, v, lson );
62 if( R > m ) query( L, R, v, rson );
63 }
64 int main(){
65 int cas;
66 scanf( "%d", &cas );
67 while( cas-- ){
68 init();
69 scanf( "%d", &n );
70 for( int i = 1; i <= n; i++ ){
71 scanf( "%d %d %d", &p[i].l, &p[i].r, &p[i].x );
72 p[i].l <<= 1, p[i].r <<= 1;
73 }
74 sort( p + 1, p + n + 1 );
75 for( int i = 1; i <= n; i++ ){
76 query( p[i].l, p[i].r, i, 0, N, 1 );
77 update( p[i].l, p[i].r, i, 0, N, 1 );
78 }
79 int ans = 0;
80 for( int i = 1; i <= n; i++ ){
81 int len1 = g[i].size();
82 for( int j = 0; j < len1; j++ ){
83 int kk = g[i][j], len2 = g[kk].size();
84 for( int k = j + 1; k < len1; k++ ){
85 for( int m = 0; m < len2; m++ ){
86 if( g[i][k] == g[kk][m] ) ans++;
87 }
88 }
89 }
90 g[i].clear();
91 }
92 printf( "%d
", ans );
93 }
94 return 0;
95 }
View Code
poj2991 Crane
线段树加几何。。( c++过了,g++超时 ) 感觉有些时候g++快点,有些时候g++很慢,搞不懂有什么差别╮(╯▽╰)╭
题意:给你一个n节组成的起重机,而每两节直接可以旋转,一开始每节都在y轴上,现在对于每次旋转第i与i+1的角度,求末端( 第N条线段的端点 )的坐标。。。
线段树的节点保存三个信息: 向量的坐标( vx, vy ) 和 向量旋转的角度( ang )。。
分析: 1.向量(x,y)则,向量 逆时针 旋转a弧度 后的向量为(cos a *x-sin a*y,sin a*x+cos a*y)
2.向量的和刚好指向这些向量头尾相连后所指向的地方,也就是把每条线段看做一个向量,那么这项向量的和正好指向末端的坐标
3.旋转第i与i+1的角度是,i+1及其上的所有向量都旋转了同样的角度
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<string>
5 #include<queue>
6 #include<cmath>
7 #include<vector>
8
9 using namespace std;
10
11 #define mnx 50005
12 #define ll long long
13 #define mod 1000000007
14 #define inf 0x3f3f3f3f
15 #define eps 1e-8
16 #define Pi acos(-1.0);
17 #define lson l, m, rt << 1
18 #define rson m+1, r, rt << 1 | 1
19
20 double vx[mnx], vy[mnx], ang[mnx], degree[mnx];
21 void rotate( int rt, double rad ){
22 rad = ( rad / 180.0 ) * Pi;
23 double x = vx[rt] * cos( rad ) - vy[rt] * sin( rad );
24 double y = vy[rt] * cos( rad ) + vx[rt] * sin( rad );
25 vx[rt] = x, vy[rt] = y;
26 }
27 void pushup( int rt ){
28 vx[rt] = vx[rt<<1] + vx[rt<<1|1];
29 vy[rt] = vy[rt<<1] + vy[rt<<1|1];
30 }
31 void pushdown( int rt ){
32 if( fabs( ang[rt] ) > eps ){
33 rotate( rt<<1, ang[rt] );
34 rotate( rt<<1|1, ang[rt] );
35 ang[rt<<1] += ang[rt];
36 ang[rt<<1|1] += ang[rt];
37 ang[rt] = 0;
38 }
39 }
40 void build( int l, int r, int rt ){
41 ang[rt] = 0;
42 if( l == r ){
43 scanf( "%lf", &vy[rt] );
44 vx[rt] = 0;
45 return ;
46 }
47 int m = ( l + r ) >> 1;
48 build( lson );
49 build( rson );
50 pushup( rt );
51 }
52 void update( int s, double a, int l, int r, int rt ){
53 if( s < l ){
54 rotate( rt, a );
55 ang[rt] += a;
56 return ;
57 }
58 pushdown( rt );
59 int m = ( l + r ) >> 1;
60 if( s < m ) update( s, a, lson );
61 update( s, a, rson );
62 pushup( rt );
63 }
64 int main(){
65 int n, q, flag = 0;
66 while( scanf( "%d %d", &n, &q ) != EOF ){
67 if( flag ) puts( "" );
68 flag = 1;
69 build( 1, n, 1 );
70 for( int i = 0; i <= n+2; i++ ) degree[i] = 180.0;
71 while( q-- ){
72 int s; double a;
73 scanf( "%d %lf", &s, &a );
74 update( s, a - degree[s+1], 1, n, 1 );
75 degree[s+1] = a;
76 printf( "%.2lf %.2lf
", vx[1], vy[1] );
77 }
78 }
79 return 0;
80 }
View Code
FZU 2163 多米诺骨牌
中文题,不解释。。线段树区间更新,离散化。。找了好久的错,发现query里面还要sum[rt] = sum[rt<<1] + sum[rt<<1|1];因为我query的时候也改了sum[rt]的值,所以要向上更新,跪了好久。。其实还是逗比了,我应该写一个区间更新的update的,在query之后,然后对[l,r]进行区间更新的,然后再对[l,l]进行单点更新,就不会wa这么久了
做法: 先按照x坐标又大到小排序,然后从右到左边查边插入线段树。。(这道题还可以用单调栈)
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #include<string>
6 #include<cmath>
7 #include<map>
8 #include<queue>
9
10 using namespace std;
11
12 #define mnx 200005
13 #define Pi acos(-1.0)
14 #define ull unsigned long long
15 #define ll long long
16 #define inf 0x3f3f3f3f
17 #define eps 1e-8
18 #define MP make_pair
19 #define lson l, m, rt << 1
20 #define rson m+1, r, rt << 1 | 1
21 #define mod 2333333
22
23 const int N = mnx - 2;
24 int ch[mnx<<2], sum[mnx<<2], col[mnx<<2], ans[mnx];
25 struct domino{
26 int x, h, id;
27 bool operator < ( const domino & b ) const{
28 return x > b.x;
29 }
30 }p[mnx];
31 int bin_search( int key, int n ){
32 return lower_bound( ch + 1, ch + n + 1, key ) - ch;
33 }
34 void pushdown( int rt ){
35 if( col[rt] ){
36 sum[rt<<1] = sum[rt<<1|1] = 0;
37 col[rt<<1] = col[rt<<1|1] = 1;
38 col[rt] = 0;
39 }
40 }
41 void update( int k, int v, int l, int r, int rt ){
42 if( l == r ){
43 sum[rt] = v;
44 return ;
45 }
46 pushdown( rt );
47 int m = ( l + r ) >> 1;
48 if( k <= m ) update( k, v, lson );
49 else update( k, v, rson );
50 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
51 }
52 int query( int L, int R, int l, int r, int rt ){
53 int ret = 0;
54 if( L <= l && R >= r ){
55 col[rt] = 1, ret = sum[rt], sum[rt] = 0;
56 return ret;
57 }
58 pushdown( rt );
59 int m = ( l + r ) >> 1;
60 if( L <= m ) ret += query( L, R, lson );
61 if( R > m ) ret += query( L, R, rson );
62 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
63 return ret;
64 }
65 int main(){
66 int n;
67 while( scanf( "%d", &n ) != EOF ){
68 memset( col, 0, sizeof(col) );
69 memset( sum, 0, sizeof(sum) );
70 int l, r, cnt = 1;
71 for( int i = 1; i <= n; i++ ){
72 scanf( "%d %d", &l, &r );
73 p[i].x = l, p[i].h = r, p[i].id = i;
74 ch[cnt++] = l, ch[cnt++] = r + l - 1;
75 }
76 sort( ch + 1, ch + cnt );
77 cnt = unique( ch + 1, ch + cnt ) - ch - 1;
78 sort( p + 1, p + n + 1 );
79 for( int i = 1; i <= n; i++ ){
80 l = bin_search( p[i].x, cnt );
81 r = bin_search( p[i].h + p[i].x - 1, cnt );
82 ans[p[i].id] = query( l, r, 1, N, 1 ) + 1;
83 update( l, ans[p[i].id], 1, N, 1 );
84 }
85 for( int i = 1; i <= n; i++ ){
86 printf( "%d%c", ans[i], i == n ? '
' : ' ' );
87 }
88 }
89 return 0;
90 }
View Code
hdu 4973 A simple simulation problem
尼玛,跪了一个晚上,终于检查出错误了。。下午的做法想线段树每个节点记录三个值l, r, sum,最后写了两个小时,没有过,哎。。晚上听小坤子讲了他的做法,敲出来了,然后一直不能ac,最后还是他帮我找出错误。。敲代码还是细心细心啊。。
做法:sum[]维护的是节点内数的个数,cnt[]维护的是这个节点内,不同数的个数的最大值,col[]记录这个区间内的数复制了多少次。。输入要更新和要询问的区间[l, r],先查找 l 在哪个节点(假设为L)上, r 在哪个节点(假设为R)上,再更新或询问( L + 1, R + 1 )这个区间
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<string>
5 #include<queue>
6 #include<algorithm>
7 #include<cmath>
8 #include<vector>
9
10 using namespace std;
11
12 #define mnx 50050
13 #define ll long long
14 #define mod 1000000007
15 #define inf 0x3f3f3f3f
16 #define eps 1e-10
17 #define Pi acos(-1.0);
18 #define lson l, m, rt << 1
19 #define rson m+1, r, rt << 1 | 1
20
21 ll sum[mnx<<2], ls, rs, cnt[mnx<<2];
22 int col[mnx<<2];
23 void pushup( int rt ){
24 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
25 cnt[rt] = max( cnt[rt<<1], cnt[rt<<1|1] );
26 }
27 void pushdown( int rt ){
28 if( col[rt] ){
29 col[rt<<1] += col[rt];
30 col[rt<<1|1] += col[rt];
31 int k = col[rt];
32 sum[rt<<1] <<= k;
33 sum[rt<<1|1] <<= k;
34 cnt[rt<<1] <<= k;
35 cnt[rt<<1|1] <<= k;
36 col[rt] = 0;
37 }
38 }
39 void build( int l, int r, int rt ){
40 col[rt] = 0;
41 if( l == r ){
42 sum[rt] = 1, cnt[rt] = 1;
43 return ;
44 }
45 int m = ( l + r ) >> 1;
46 build( lson ); build( rson );
47 pushup( rt );
48 }
49 int find( int t, int x, int l, int r, int rt ){
50 if( l == r ){
51 if( t == 0 ){
52 rs = sum[rt] - x + 1;
53 }
54 if( t == 1 ){
55 ls = x;
56 }
57 return l;
58 }
59 pushdown( rt );
60 int m = ( l + r ) >> 1;
61 if( x <= sum[rt<<1] ) return find( t, x, lson );
62 else return find( t, x - sum[rt<<1], rson );
63 }
64 void update1( int x, int v, int l, int r, int rt ){
65 if( l == r ){
66 sum[rt] += v;
67 cnt[rt] += v;
68 return ;
69 }
70 pushdown( rt );
71 int m = ( l + r ) >> 1;
72 if( x <= m ) update1( x, v, lson );
73 else update1( x, v, rson );
74 pushup( rt );
75 }
76 void update2( int L, int R, int l, int r, int rt ){
77 if( L <= l && R >= r ){
78 col[rt] += 1;
79 sum[rt] <<= 1;
80 cnt[rt] <<= 1;
81 return ;
82 }
83 pushdown( rt );
84 int m = ( l + r ) >> 1;
85 if( L <= m ) update2( L, R, lson );
86 if( R > m ) update2( L, R, rson );
87 pushup( rt );
88 }
89 ll query( int L, int R, int l, int r, int rt ){
90 if( L <= l && R >= r ){
91 return cnt[rt];
92 }
93 pushdown( rt );
94 int m = ( l + r ) >> 1; ll ret = -1;
95 if( L <= m ) ret = max( ret, query( L, R, lson ) );
96 if( R > m ) ret = max( ret, query( L, R, rson ) );
97 return ret;
98 }
99 int main(){
100 //freopen( "out.txt", "w", stdout );
101 int cas, kcnt = 1, n, m;
102 scanf( "%d", &cas );
103 while( cas-- ){
104 scanf( "%d %d", &n, &m );
105 build( 1, n, 1 );
106 char ch[2];
107 int l, r;
108 printf( "Case #%d:
", kcnt++ );
109 while( m-- ){
110 scanf( "%s %d %d", &ch, &l, &r );
111 if( ch[0] == 'D' ){
112 int L = find( 0, l, 1, n, 1 );
113 int R = find( 1, r, 1, n, 1 );
114 if( L == R ){
115 update1( L, r - l + 1, 1, n, 1 );
116 }
117 else{
118 update1( L, rs, 1, n, 1 );
119 update1( R, ls, 1, n, 1 );
120 if( L + 1 <= R - 1 ) update2( L + 1, R - 1, 1, n, 1 );
121 }
122 }
123 else{
124 int L = find( 0, l, 1, n, 1 );
125 int R = find( 1, r, 1, n, 1 );
126 if( L == R ){
127 printf( "%d
", r - l + 1 );
128 }
129 else{
130 ll ans = max( ls, rs );
131 if( L + 1 <= R - 1 ) ans = max( ans, query( L + 1, R - 1, 1, n, 1 ) );
132 printf( "%I64d
", ans );
133 }
134 }
135 }
136 }
137 return 0;
138 }
View Code
ZOJ 3686 A Simple Tree Problem
给你一棵树,所有的节点初始为0。给你一个节点u,有两种操作,一种是把u及其子节点全部翻转( 0 -> 1, 1 -> 0 ),第二种操作就是问你 u及其子节点有多少个1。。
先dfs整棵树,记录每棵子树的区间,假设有n个节点,树根在的节点就是[1,n]。然后就可以用线段树成段更新了。翻转的时候是sum[rt] = r - l + 1 - sum[rt];
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <vector>
6 #include <algorithm>
7
8 using namespace std;
9
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 100010
15
16 int n, fst[mnx], vv[mnx], nxt[mnx], e;
17 struct node{
18 int L, R;
19 }g[mnx];
20 void add( int u, int v ){
21 vv[e] = v, nxt[e] = fst[u], fst[u] = e++;
22 }
23 int c;
24 int dfs( int u ){
25 g[u].L = ++c;
26 for( int i = fst[u]; i != -1; i = nxt[i] )
27 dfs( vv[i] );
28 g[u].R = c;
29 }
30 int Xor[mnx<<2], sum[mnx<<2];
31 void pushdown( int rt, int L, int R ){
32 int m = ( L + R ) >> 1;
33 if( Xor[rt] ){
34 Xor[rt<<1] ^= 1, Xor[rt<<1|1] ^= 1, Xor[rt] = 0;
35 sum[rt<<1] = m - L + 1 - sum[rt<<1];
36 sum[rt<<1|1] = R - m - sum[rt<<1|1];
37 }
38 }
39 void pushup( int rt ){
40 sum[rt] = sum[rt<<1] + sum[rt<<1|1];
41 }
42 void update( int L, int R, int l, int r, int rt ){
43 if( L <= l && R >= r ){
44 Xor[rt] ^= 1;
45 sum[rt] = r - l + 1 - sum[rt];
46 return ;
47 }
48 pushdown( rt, l, r );
49 int m = ( l + r ) >> 1;
50 if( L <= m ) update( L, R, lson );
51 if( R > m ) update( L, R, rson );
52 pushup( rt );
53 }
54 int query( int L, int R, int l, int r, int rt ){
55 if( L <= l && R >= r ){
56 return sum[rt];
57 }
58 pushdown( rt, l, r );
59 int m = ( l + r ) >> 1, ret = 0;
60 if( L <= m ) ret += query( L, R, lson );
61 if( R > m ) ret += query( L, R, rson );
62 // pushup( rt );
63 return ret;
64 }
65 int main(){
66 int m;
67 while( scanf( "%d%d", &n, &m ) != EOF ){
68 memset( sum, 0, sizeof(sum) );
69 memset( Xor, 0, sizeof(Xor) );
70 memset( fst, -1, sizeof(fst) );
71 c = e = 0;
72 int v;
73 for( int i = 2; i <= n; ++i ){
74 scanf( "%d", &v );
75 add( v, i );
76 }
77 dfs( 1 );
78 while( m-- ){
79 char c[3];
80 scanf( "%s", c );
81 scanf( "%d", &v );
82 if( c[0] == 'o' )
83 update( g[v].L, g[v].R, 1, n, 1 );
84 else
85 printf( "%d
", query( g[v].L, g[v].R, 1, n, 1 ) );
86 }
87 puts( "" );
88 }
89 return 0;
90 }
View Code