首页 > 代码库 > HDU 3911 Black And White（线段树区间合并）
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<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int mod = 1000000007;
const int maxn=1e5+10;
int lmax_1[maxn<<2],rmax_1[maxn<<2];
int lmax_0[maxn<<2],rmax_0[maxn<<2];
int max_1[maxn<<2],max_0[maxn<<2];
int col[maxn<<2];
int n,m,os;
void pushup(int rs,int m)
{
lmax_1[rs]=lmax_1[rs<<1];//处理左边一类前缀
lmax_0[rs]=lmax_0[rs<<1];
if(lmax_1[rs<<1]==m-(m>>1)) lmax_1[rs]+=lmax_1[rs<<1|1];
if(lmax_0[rs<<1]==m-(m>>1)) lmax_0[rs]+=lmax_0[rs<<1|1];
rmax_1[rs]=rmax_1[rs<<1|1];//处理右边一类后缀
rmax_0[rs]=rmax_0[rs<<1|1];
if(rmax_1[rs<<1|1]==(m>>1)) rmax_1[rs]+=rmax_1[rs<<1];
if(rmax_0[rs<<1|1]==(m>>1)) rmax_0[rs]+=rmax_0[rs<<1];
max_1[rs]=max(max_1[rs<<1],max_1[rs<<1|1]);//处理整个区间的值
max_1[rs]=max(max_1[rs],rmax_1[rs<<1]+lmax_1[rs<<1|1]);
max_0[rs]=max(max_0[rs<<1],max_0[rs<<1|1]);
max_0[rs]=max(max_0[rs],rmax_0[rs<<1]+lmax_0[rs<<1|1]);
}
void work(int rs)
{
swap(lmax_1[rs],lmax_0[rs]);
swap(rmax_1[rs],rmax_0[rs]);
swap(max_1[rs],max_0[rs]);
}
void push_down(int rs)
{
if(col[rs])
{
col[rs<<1]^=1;col[rs<<1|1]^=1;
col[rs]=0;work(rs<<1);work(rs<<1|1);
}
}
void build(int rs,int l,int r)
{
col[rs]=0;
if(l==r)
{
scanf("%d",&os);
if(os==1)
{
lmax_1[rs]=rmax_1[rs]=max_1[rs]=1;
lmax_0[rs]=rmax_0[rs]=max_0[rs]=0;
}
else
{
lmax_1[rs]=rmax_1[rs]=max_1[rs]=0;
lmax_0[rs]=rmax_0[rs]=max_0[rs]=1;
}
return ;
}
int mid=(l+r)>>1;
build(rs<<1,l,mid);
build(rs<<1|1,mid+1,r);
pushup(rs,r-l+1);
}
void update(int x,int y,int l,int r,int rs)
{
if(l>=x&&r<=y)
{
col[rs]^=1;
work(rs);//交换值
return ;
}
push_down(rs);
int mid=(l+r)>>1;
if(x<=mid) update(x,y,l,mid,rs<<1);
if(y>mid) update(x,y,mid+1,r,rs<<1|1);
pushup(rs,r-l+1);
}
int query(int x,int y,int l,int r,int rs)
{
if(l>=x&&r<=y)
return max_1[rs];
push_down(rs);
int mid=(l+r)>>1;
if(x>mid) return query(x,y,mid+1,r,rs<<1|1);
if(y<=mid) return query(x,y,l,mid,rs<<1);
int t1=query(x,y,l,mid,rs<<1);
int t2=query(x,y,mid+1,r,rs<<1|1);
int r1=min(mid-x+1,rmax_1[rs<<1]);//以mid为分割点
int r2=min(y-mid,lmax_1[rs<<1|1]);
int res=max(max(t1,t2),r1+r2);
return res;
}
int main()
{
int op,x,y;
while(~scanf("%d",&n))
{
build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
update(x,y,1,n,1);
else
printf("%d\n",query(x,y,1,n,1));
}
}
return 0;
}
HDU 3911 Black And White（线段树区间合并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。