HDU 3911 Black And White(線段樹區間合並)
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
4
1 0 1 0
5
0 1 4
1 2 3
0 1 4
1 3 3
0 4 4
Sample Output
1
2
0
線段樹區間合並:對於每個區間[l,r]所對應的rs,我們給出6個量:
lmax_1:左起的1的最大前綴,lmax_0:左起的0的最大前綴;
rmax_1:右起的1的最大後綴rmax_0:右起的0的最大後綴;
max_1:區間的1的最大連續值,max_0:區間的0的最大連續值
我們的任務就是不斷地更新求值。
#include
#include
#include
#include
#include
#include
#include
#include
#include