hdu 3911 Black And White

Black And White

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3561 Accepted Submission(s): 1062

Problem Description

There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

Input

There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

Output

When x=0 output a number means the longest length of black stones in range [i,j].

Sample Input

1 0 1 0

0 1 4

1 2 3

0 1 4

1 3 3

0 4 4

Sample Output

Source

2011 Multi-University Training Contest 8 - Host by HUST

  1 /**
  2 题意：两种操作
  3 0 l ,r 查找区间[ L , R ]里最长的连续1的数目。
  4 1 l ,r 更新区间[ L , R ]里的数字。0变成1,  1变成0
  5 
  6 思路：
  7 由于连续1的存在，我们需要保存lnum, rnum.  lmaxn, rmaxn maxn;
  8 加上1操作，我们还要有个延迟标记才行。
  9 bool  setFlag;
 10 
 11 如果就设置这些参数。在更新的时候，
 12 我们必须要找到一段连续相等数字的区间，对它进行延迟标记。
 13 i f ( f[n].maxn == f[n].len || f[n].maxn == 0 )
 14 
 15  这样的话，我们有可能更新到叶子节点。这样的时间就多了。
 16  其实，我们最期望的就是一旦找到区间[ L ,R ]的时候，就进行延迟
 17  标记，然后返回。
 18 
 19  由此，我们还要加上统计0个数的数据。
 20  Zlmaxn,Zrmaxn,Zmaxn;
 21  1的操作本质上也是 0  和 1的转化，所以交换它们的值就可以了。
 22 
 23  同时，我们需要注意，对于setFlag ,只有奇数次的时候才标记为ture;
 24 
 25 **/
 26 
 27 #include<iostream>
 28 #include<stdio.h>
 29 #include<cstring>
 30 #include<cstdlib>
 31 using namespace std;
 32 
 33 struct node
 34 {
 35     int l,r,len;
 36     int lnum,rnum;
 37     int lmaxn,rmaxn,maxn;
 38     int Zlmaxn,Zrmaxn,Zmaxn;
 39     bool setFlag;
 40 }f[100002*4];
 41 int date;
 42 
 43 void up(int n)
 44 {
 45     f[n].lnum = f[n*2].lnum;
 46     f[n].rnum = f[n*2+1].rnum;
 47 
 48     f[n].lmaxn = ( f[n*2].lmaxn==f[n*2].len && f[n*2].rnum==f[n*2+1].lnum ) ?
 49                      f[n*2].lmaxn+f[n*2+1].lmaxn:f[n*2].lmaxn;
 50     f[n].rmaxn = ( f[n*2+1].rmaxn == f[n*2+1].len && f[n*2].rnum == f[n*2+1].lnum) ?
 51                      f[n*2+1].rmaxn+f[n*2].rmaxn : f[n*2+1].rmaxn;
 52     f[n].maxn = max(f[n*2].maxn,f[n*2+1].maxn);
 53     if(f[n*2].rnum == 1 && f[n*2+1].lnum == 1)
 54         f[n].maxn = max(f[n].maxn,f[n*2].rmaxn+f[n*2+1].lmaxn);
 55 
 56     f[n].Zlmaxn = ( f[n*2].Zlmaxn==f[n*2].len && f[n*2].rnum==f[n*2+1].lnum ) ?
 57                      f[n*2].Zlmaxn+f[n*2+1].Zlmaxn:f[n*2].Zlmaxn;
 58     f[n].Zrmaxn = ( f[n*2+1].Zrmaxn == f[n*2+1].len && f[n*2].rnum == f[n*2+1].lnum) ?
 59                      f[n*2+1].Zrmaxn+f[n*2].Zrmaxn : f[n*2+1].Zrmaxn;
 60     f[n].Zmaxn = max(f[n*2].Zmaxn,f[n*2+1].Zmaxn);
 61     if(f[n*2].rnum == 0 && f[n*2+1].lnum == 0)
 62         f[n].Zmaxn = max(f[n].Zmaxn,f[n*2].Zrmaxn+f[n*2+1].Zlmaxn);
 63 }
 64 void build(int l,int r,int n)
 65 {
 66     int mid=(l+r)/2;
 67     f[n].l = l;
 68     f[n].r = r;
 69     f[n].len = f[n].r-f[n].l+1;
 70     f[n].setFlag = false;
 71     f[n].lnum=f[n].rnum=0;
 72     f[n].lmaxn=f[n].rmaxn=f[n].maxn=0;
 73     f[n].Zlmaxn=f[n].Zrmaxn=f[n].Zmaxn=0;
 74     if(l==r)
 75     {
 76         scanf("%d",&date);
 77         f[n].lnum=f[n].rnum=date;
 78         f[n].lmaxn=f[n].rmaxn=f[n].maxn=date;
 79         f[n].Zlmaxn=f[n].Zrmaxn=f[n].Zmaxn=(date^1);
 80         return;
 81     }
 82     build(l,mid,n*2);
 83     build(mid+1,r,n*2+1);
 84     up(n);
 85 }
 86 
 87 void down(int n)
 88 {
 89     f[n*2].setFlag = f[n*2].setFlag^1;
 90     /**传递的是奇数次，偶数次就抵消了，不需要向下更新**/
 91     swap(f[n*2].lmaxn,f[n*2].Zlmaxn);
 92     swap(f[n*2].rmaxn,f[n*2].Zrmaxn);
 93     swap(f[n*2].maxn,f[n*2].Zmaxn);
 94     f[n*2].lnum = (f[n*2].lnum^1);
 95     f[n*2].rnum = (f[n*2].rnum^1);
 96 
 97     f[n*2+1].setFlag = f[n*2+1].setFlag^1;
 98     /**传递的是奇数次，偶数次就抵消了，不需要向下更新**/
 99     swap(f[n*2+1].lmaxn,f[n*2+1].Zlmaxn);
100     swap(f[n*2+1].rmaxn,f[n*2+1].Zrmaxn);
101     swap(f[n*2+1].maxn,f[n*2+1].Zmaxn);
102     f[n*2+1].lnum=(f[n*2+1].lnum^1);
103     f[n*2+1].rnum=(f[n*2+1].rnum^1);
104 
105     f[n].setFlag = false;
106 }
107 void update(int l,int r,int n)
108 {
109     int mid=(f[n].l + f[n].r)/2;
110     if(f[n].l == l && f[n].r == r)
111     {
112         f[n].setFlag = (f[n].setFlag^1);
113         /**传递的是奇数次，偶数次就抵消了，不需要向下更新**/
114         f[n].lnum=(f[n].lnum^1);
115         f[n].rnum=(f[n].rnum^1);
116         swap(f[n].lmaxn,f[n].Zlmaxn);
117         swap(f[n].rmaxn,f[n].Zrmaxn);
118         swap(f[n].maxn,f[n].Zmaxn);
119         return ;
120     }
121     if(f[n].setFlag==true) down(n);
122     if(mid>=r) update(l,r,n*2);
123     else if(mid<l) update(l,r,n*2+1);
124     else
125     {
126         update(l,mid,n*2);
127         update(mid+1,r,n*2+1);
128     }
129     up(n);
130 }
131 
132 int query(int l,int r,int n)
133 {
134     int mid=(f[n].l + f[n].r)/2;
135     if(f[n].l == l && f[n].r==r)
136     {
137          return f[n].maxn;
138     }
139     if(f[n].setFlag==true) down(n);
140     if(mid>=r) return query(l,r,n*2);
141     else if(mid<l) return query(l,r,n*2+1);
142     else
143     {
144         int lmaxn = query(l,mid,n*2);
145         int rmaxn = query(mid+1,r,n*2+1);
146         int maxn = max(lmaxn,rmaxn);
147         if(f[n*2].rnum==1 && f[n*2+1].lnum ==1)
148             maxn = max(  maxn,min(mid-l+1,f[n*2].rmaxn)+min(r-mid,f[n*2+1].lmaxn)  );
149         return maxn;
150     }
151 }
152 
153 int main()
154 {
155     int n,m,l,r,size1;
156     while(scanf("%d",&n)>0)
157     {
158         build(1,n,1);
159         scanf("%d",&m);
160         while(m--)
161         {
162             scanf("%d%d%d",&size1,&l,&r);
163             if(size1==1)
164                 update(l,r,1);
165             else if(size1==0)
166                 printf("%d\n",query(l,r,1));
167         }
168     }
169     return 0;
170 }