首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

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

2012-08-11 
hdu3911 Black And White高频率出现的线段树难题Black And WhiteTime Limit: 9000/3000 MS (Java/Others)M

hdu3911 Black And White 高频率出现的线段树难题
Black And WhiteTime Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1811    Accepted Submission(s): 609


Problem DescriptionInputOutputSample InputSample OutputSource#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;
}

热点排行