当前位置：首页 -> 基础 -> c++编程基础

HDU 3911 Black And White（线段树区间合并）

2015-01-24 13:18:47 · 作者: · 浏览: 5
标签: 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
           #include
           
             #include
            
              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
             
              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; }