http://acm.hdu.edu.cn/showproblem.php?pid=3911久违的线段树啊，亲 好久没写线段树了，都不会写了。。。 在队友的指导下，艰难地写完了。。。
1  /**//*
2 author: AmazingCaddy
3 time: 2011/8/13 16:10
4 */
5 #include <cstdio>
6#include <complex>
7#include <cstdlib>
8#include <iostream>
9#include <cstring>
10#include <string>
11#include <algorithm>
12#include <cmath>
13#include <ctime>
14#include <vector>
15#include <map>
16#include <queue>
17using namespace std;
18
19const int maxn = 100100;
20
21struct node
22 {
23 int l, r;
24 int bmax, bl, br; // 最长的连续黑色
25 int wmax, wl, wr; // 最长的连续白色
26 bool flag; // 标记是否取反
27};
28
29node tree[ maxn << 2 ];
30int f[ maxn ];
31
32void Swap( int v )
33{
34 swap( tree[ v ].bmax, tree[ v ].wmax );
35 swap( tree[ v ].bl, tree[ v ].wl );
36 swap( tree[ v ].br, tree[ v ].wr );
37}
38
39void push_down( int sonv )
40{
41 tree[ sonv ].flag = !tree[ sonv ].flag;
42 Swap( sonv );
43}
44
45void push_up( int v )
46{
47 // 黑色部分
48 // 总长度
49 tree[ v ].bmax = max( tree[ v << 1 ].bmax, tree[ v << 1 | 1 ].bmax );
50 tree[ v ].bmax = max( tree[ v ].bmax, tree[ v << 1 ].br + tree[ v << 1 | 1 ].bl );
51 // 左端
52 if( tree[ v << 1 ].bl == tree[ v << 1 ].r - tree[ v << 1 ].l )
53 tree[ v ].bl = tree[ v << 1 ].bl + tree[ v << 1 | 1 ].bl;
54 else tree[ v ].bl = tree[ v << 1 ].bl;
55 // 右端
56 if( tree[ v << 1 | 1 ].br == tree[ v << 1 | 1 ].r - tree[ v << 1 | 1 ].l )
57 tree[ v ].br = tree[ v << 1 ].br + tree[ v << 1 | 1 ].br;
58 else tree[ v ].br = tree[ v << 1 | 1 ].br;
59
60 // 白色部分
61 // 总长度
62 tree[ v ].wmax = max( tree[ v << 1 ].wmax, tree[ v << 1 | 1 ].wmax );
63 tree[ v ].wmax = max( tree[ v ].wmax, tree[ v << 1 ].wr + tree[ v << 1 | 1 ].wl );
64 // 左端
65 if( tree[ v << 1 ].wl == tree[ v << 1 ].r - tree[ v << 1 ].l )
66 tree[ v ].wl = tree[ v << 1 ].wl + tree[ v << 1 | 1 ].wl;
67 else tree[ v ].wl = tree[ v << 1 ].wl;
68 // 右端
69 if( tree[ v << 1 | 1 ].wr == tree[ v << 1 | 1 ].r - tree[ v << 1 | 1 ].l )
70 tree[ v ].wr = tree[ v << 1 ].wr + tree[ v << 1 | 1 ].wr;
71 else tree[ v ].wr = tree[ v << 1 | 1 ].wr;
72}
73
74void make_tree( int v, int l, int r )
75{
76 tree[ v ].l = l;
77 tree[ v ].r = r;
78 tree[ v ].flag = false;
79 if( l + 1 != r )
80  {
81 int mid = ( l + r ) >> 1;
82 make_tree( v << 1, l, mid );
83 make_tree( v << 1 | 1, mid, r );
84 push_up( v );
85 }
86 else
87 {
88 if( f[ l ] )// 黑色
89 {
90 tree[ v ].bmax = tree[ v ].bl = tree[ v ].br = 1;
91 tree[ v ].wmax = tree[ v ].wl = tree[ v ].wr = 0;
92 }
93 else // 白色
94 {
95 tree[ v ].wmax = tree[ v ].wl = tree[ v ].wr = 1;
96 tree[ v ].bmax = tree[ v ].bl = tree[ v ].br = 0;
97 }
98 }
99}
100
101void update( int v, int l, int r )
102{
103 if( tree[ v ].l == l && tree[ v ].r == r )
104 {
105 tree[ v ].flag = !tree[ v ].flag;
106 Swap( v );
107 return;
108 }
109
110 if( tree[ v ].flag )
111 {
112 tree[ v ].flag = false;
113 push_down( v << 1 );
114 push_down( v << 1 | 1 );
115 }
116
117 int mid = ( tree[ v ].l + tree[ v ].r ) >> 1;
118 if( r <= mid ) update( v << 1, l, r );
119 else if( l >= mid ) update( v << 1 | 1, l, r );
120 else
121 {
122 update( v << 1, l, mid );
123 update( v << 1 | 1, mid, r );
124 }
125 push_up( v );
126}
127
128int query( int v, int l, int r )
129{
130 if( tree[ v ].l == l && tree[ v ].r == r )
131 {
132 return tree[ v ].bmax;
133 }
134
135 if( tree[ v ].flag )
136 {
137 tree[ v ].flag = false;
138 push_down( v << 1 );
139 push_down( v << 1 | 1 );
140 }
141
142 int mid = ( tree[ v ].l + tree[ v ].r ) >> 1;
143 if( r <= mid ) return query( v << 1, l, r );
144 if( l >= mid ) return query( v << 1 | 1, l, r );
145 int t1 = max( query( v << 1, l, mid ), query( v << 1 | 1, mid, r ) );
146 int t2 = min( tree[ v << 1 ].br, mid - l ) + min( tree[ v << 1 | 1 ].bl, r - mid );
147 return max( t1, t2 );
148}
149
150int main(int argc, char *argv[])
151{
152// freopen( "BAW.in", "r", stdin );
153// freopen( "out", "w", stdout );
154 int n, m;
155 int op, a, b;
156 while( scanf( "%d", &n ) != EOF )
157 {
158 for( int i = 0; i < n; i++ )
159 scanf( "%d", &f[ i ] );
160 make_tree( 1, 0, n );
161 scanf( "%d", &m );
162 for( int i = 0; i < m; i++ )
163 {
164 scanf( "%d%d%d", &op, &a, &b );
165 if( op ) update( 1, a - 1, b );
166 else printf( "%d\n", query( 1, a - 1, b ) );
167 }
168 }
169 return 0;
170}
171
|