题目：http://acm.hdu.edu.cn/showproblem.php?pid=3911
题意：给定序列（只有0，1），修改是将0变成1，1变成0，询问是查询区间最大连续1的数目。
用线段树维护7个变量：
第1，2个是区间的最大前缀0，和前缀1
第3，4个是区间的最大后缀0，和后缀1
第5，6个是区间的最大连续0，和最大连续1
第7个是lazy（区间更新必备）
由于我们存了1，0的相关值，在向下更改时只需将1，0的有关值全部交换即可。
而在询问时要注意询问区间在树上被分割时要计算左边连续1与右边连续1的最大和中间合并（左边后面最大1与右边前面最大1）的值再取最大。
剩下的就是细心了。
代码：
1 ///http://acm.hdu.edu.cn/showproblem.php?pid=3911
2 #include<iostream>
3 #include<cstdio>
4 #include<string.h>
5 using namespace std;
6 const int maxn=1e5+5;
7 struct Tree{
8 int l0,r0;
9 int l1,r1;
10 int ml0,ml1;
11 int lazy;
12 }tree[maxn<<2];
13 int val;
14 void up(int k,int l,int r){
15 int mid=(l+r)>>1;
16 ///前缀最大1的个数
17 tree[k].l1=tree[k<<1].l1;
18 if(tree[k].l1==mid-l+1){
19 tree[k].l1+=tree[k<<1|1].l1;
20 }
21 ///前缀最大0的个数
22 tree[k].l0=tree[k<<1].l0;
23 if(tree[k].l0==mid-l+1){
24 tree[k].l0+=tree[k<<1|1].l0;
25 }
26 ///后缀最大1的个数
27 tree[k].r1=tree[k<<1|1].r1;
28 if(tree[k].r1==r-mid){
29 tree[k].r1+=tree[k<<1].r1;
30 }
31 ///后缀最大0的个数
32 tree[k].r0=tree[k<<1|1].r0;
33 if(tree[k].r0==r-mid){
34 tree[k].r0+=tree[k<<1].r0;
35 }
36 ///区间最大1和最大0的个数
37 tree[k].ml1=max(max(tree[k<<1].ml1,tree[k<<1|1].ml1),tree[k<<1].r1+tree[k<<1|1].l1);
38 tree[k].ml0=max(max(tree[k<<1].ml0,tree[k<<1|1].ml0),tree[k<<1].r0+tree[k<<1|1].l0);
39 }
40
41 void _swap(int k){
42 swap(tree[k].l0,tree[k].l1);
43 swap(tree[k].r0,tree[k].r1);
44 swap(tree[k].ml0,tree[k].ml1);
45 }
46
47 void pushdowm(int k,int l,int r){
48 if(l!=r){
49 tree[k<<1].lazy^=1;
50 tree[k<<1|1].lazy^=1;
51 _swap(k<<1);
52 _swap(k<<1|1);
53 tree[k].lazy=0;
54 }
55 }
56
57 void build(int k,int l,int r){
58 tree[k].lazy=0;
59 if(l==r){
60 scanf("%d",&val);
61 if(val==1){
62 tree[k].l1=tree[k].r1=tree[k].ml1=1;
63 tree[k].l0=tree[k].r0=tree[k].ml0=0;
64
65 }else{
66 tree[k].l1=tree[k].r1=tree[k].ml1=0;
67 tree[k].l0=tree[k].r0=tree[k].ml0=1;
68 }
69 return ;
70 }
71 int mid=(l+r)>>1;
72 build(k<<1,l,mid);
73 build(k<<1|1,mid+1,r);
74 up(k,l,r);
75 }
76
77 void update(int k,int l,int r,int L,int R){
78 if(l>=L&&r<=R){
79 tree[k].lazy^=1;
80 _swap(k);
81 return ;
82 }
83 if(tree[k].lazy) pushdowm(k,l,r);
84 int mid=(l+r)>>1;
85 if(mid>=R) update(k<<1,l,mid,L,R);
86 else if(mid<L) update(k<<1|1,mid+1,r,L,R);
87 else{
88 update(k<<1,l,mid,L,R);
89 update(k<<1|1,mid+1,r,L,R);
90 }
91 up(k,l,r);
92 }
93
94 int query(int k,int l,int r,int L,int R){
95 if(l>=L&&r<=R){
96 return tree[k].ml1;
97 }
98 if(tree[k].lazy) pushdowm(k,l,r);
99 int mid=(l+r)>>1;
100 if(mid>=R) return query(k<<1,l,mid,L,R);
101 else if(mid<L) return query(k<<1|1,mid+1,r,L,R);
102 else{
103 int m1 = query(k<<1,l,mid,L,R);
104 int m2 = query(k<<1|1,mid+1,r,L,R);
105 int m3=min(mid-L+1,tree[k<<1].r1);
106 int m4=min(R-mid,tree[k<<1|1].l1);
107 return max(max(m1,m2),m3+m4);
108 }
109 up(k,l,r);
110 }
111
112
113 int main(){
114 int N;
115 while(scanf("%d",&N)!=EOF){
116 build(1,1,N);
117 int M,q,L,R;
118 scanf("%d",&M);
119 while(M--){
120 scanf("%d%d%d",&q,&L,&R);
121 if(q==1){
122 update(1,1,N,L,R);
123 }else{
124 printf("%d\n",query(1,1,N,L,R));
125 }
126 }
127 }
128 return 0;
129 }
