hdu3911 Black And White 高频率出现的线段树难题

Black And White

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

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

41 0 1 050 1 41 2 30 1 41 3 30 4 4

Sample Output

120

Source

#include<stdio.h>
struct haha
{
int left;
int right;
int l_b;//、 lb表示区间从左边开始连续的1的个数 如当前区间为1-10 那么这个就代表包含1的最长1串
int r_b;//、 rb表示区间从右边开始连续的1的个数 如当前区间为1-10 那么这个就代表包含10的最长1串
int l_w;//、 lw表示区间从左边开始连续的0的个数
int r_w;//、 rw表示区间从右边开始连续的0的个数
int maxb;
int maxw;
int cnt;
/*cnt表示区间被访问的次数，这里利用它实现lazy思xiang
　　这里简述一下lazy思想：每次访问的时候不用都更新到最低层的元线段，每次只访问到恰好的区间，
在这里设一个标志，表示这次更新只访问到了该区间！那么当再次访问该区间的时候就需要将该标志往其子区间传递*/
}tree[100000*4];
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
int min(int a,int b)
{
if(a<b) return a;
else return b;
}
void update(int nd)
{
int left_len,right_len;
tree[nd].maxb=max(max(tree[nd*2].maxb,tree[nd*2+1].maxb),tree[nd*2].r_b+tree[nd*2+1].l_b);
tree[nd].maxw=max(max(tree[nd*2].maxw,tree[nd*2+1].maxw),tree[nd*2].r_w+tree[nd*2+1].l_w);
left_len=tree[nd*2].right-tree[nd*2].left+1; right_len=tree[nd*2+1].right-tree[nd*2+1].left+1;
tree[nd].l_b=tree[nd*2].l_b; if(tree[nd*2].l_b==left_len) tree[nd].l_b+=tree[nd*2+1].l_b;
tree[nd].l_w=tree[nd*2].l_w; if(tree[nd*2].l_w==left_len) tree[nd].l_w+=tree[nd*2+1].l_w;
tree[nd].r_b=tree[nd*2+1].r_b; if(tree[nd*2+1].r_b==right_len) tree[nd].r_b+=tree[nd*2].r_b;
tree[nd].r_w=tree[nd*2+1].r_w; if(tree[nd*2+1].r_w==right_len) tree[nd].r_w+=tree[nd*2].r_w;
}
void build(int nd,int left,int right)
{
int mid,num;
tree[nd].left=left;tree[nd].right=right; tree[nd].cnt=0;
if(left==right)
{
scanf("%d",&num);
if(num)
{tree[nd].maxb=tree[nd].l_b=tree[nd].r_b=1; tree[nd].maxw=tree[nd].l_w=tree[nd].r_w=0; }
else
{tree[nd].maxw=tree[nd].l_w=tree[nd].r_w=1; tree[nd].maxb=tree[nd].l_b=tree[nd].r_b=0; }
return;
}
mid=(left+right)/2;
build(nd*2,left,mid);
build(nd*2+1,mid+1,right);//是mid+1 RUNTIEM ERROR 了好几次
update(nd);
}
void change(int nd)
{
int temp;
temp=tree[nd].l_b;tree[nd].l_b=tree[nd].l_w;tree[nd].l_w=temp;
temp=tree[nd].maxb;tree[nd].maxb=tree[nd].maxw;tree[nd].maxw=temp;
temp=tree[nd].r_b;tree[nd].r_b=tree[nd].r_w;tree[nd].r_w=temp;
tree[nd].cnt=!tree[nd].cnt;
}
void update2(int nd,int left,int right)
{
int mid;
if(tree[nd].left==left&&tree[nd].right==right)
{
change(nd);
return ;
}
if(tree[nd].cnt) {change(nd*2);change(nd*2+1);tree[nd].cnt=0;}
mid=(tree[nd].left+tree[nd].right)/2;
if(right<=mid) update2(nd*2,left,right);
else if(left>mid) update2(nd*2+1,left,right);
else {update2(nd*2,left,mid);update2(nd*2+1,mid+1,right);}//是mid+1 RUNTIEM ERROR 了好几次
update(nd);
}
int query(int nd,int left,int right)
{
int mid,lr,rr;
if(tree[nd].left==left&&tree[nd].right==right)
return tree[nd].maxb;
if(tree[nd].cnt) {change(nd*2);change(nd*2+1);tree[nd].cnt=0;}
mid=(tree[nd].right+tree[nd].left)/2;
if(right<=mid) return query(nd*2,left,right);
else if(left>mid)return query(nd*2+1,left,right);
else
{
lr=query(nd*2,left,mid);
rr=query(nd*2+1,mid+1,right);
return max(max(min(tree[nd*2].r_b,lr)+min(tree[nd*2+1].l_b,rr),lr),rr);//这句话真心不懂啊!
// return max(max(tree[nd*2].r_b+tree[nd*2+1].l_b,lr),rr);
}
}
int main()
{
int n,i,opr,m,left,right;
while(scanf("%d",&n)!=EOF)
{
build(1,1,n);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&opr,&left,&right);
if(opr) update2(1,left,right);
else printf("%d\n",query(1,left,right));
}
}
return 0;
}