Sequence operation

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4393 Accepted Submission(s): 1272

Problem Description

lxhgww got a sequence contains n characters which are all '0's or '1's.

We have five operations here:

Change operations:

0 a b change all characters into '0's in [a , b]

1 a b change all characters into '1's in [a , b]

2 a b change all '0's into '1's and change all '1's into '0's in [a, b]

Output operations:

3 a b output the number of '1's in [a, b]

4 a b output the length of the longest continuous '1' string in [a , b]

Input

T(T<=10) in the first line is the case number.

Each case has two integers in the first line: n and m (1 <= n , m <= 100000).

The next line contains n characters, '0' or '1' separated by spaces.

Then m lines are the operations:

op a b: 0 <= op <= 4 , 0 <= a <= b < n.

Sample Input

       1 
10 
0 0 1 1 0 1 0 1 1 
0 2 
0 5 
2 2 
0 4 
3 6 
3 7 
2 8 
0 5 
5 6 
3 9 

Sample Output

5

Output

For each output operation , output the result.

hdu3911的变形，线段树的合并+延迟标记。

题意：

给你5总操作

x l,r

x==0 将区间[l,r]全部置为0

x==1 将区间[l,r]全部置为1

x==2 将区间[l,r]0的置换为1， 1的置换为0

~~~~~~~~~~~(华丽的分割线)

x==3 输出区间[l,r] 1的个数

x==4 输出区间[l,r] 最长的连续的 1 的个数

思路：hdu3911的变形，建议先做3911试试手。

变量color为延迟标记

当color为 ZERO 代表该区间全部都是0 ，

那么其区间的左端点右端点的值为0，而且统计1的三个变量的值都为0: one_max , one_lmax, one_rmax;

当color为 ONE 代表该区间全部都是1，同理可知。

当color为 HH 代码该区间的值是置反的。则统计1的三个变量，和统计0的三个变量进行交换。不理解，建议动手画画图。

在向下更新的时候，HH的情况也需要特别的注意。

如果该区间color的值原来为ZERO，那么又遇到了HH，那么变成ONE就可以了。

如果该区间color的值原来是ONE，那么又遇到了HH，就变成ZERO.

如果该区间color的值原来是HH , 那么就要变成0，

如果该区间color的值原来是0，那么变成HH。

写了好长的代码，方法比较笨，时间花销就多了一些。写过最长的代码了，363行。

我想，在比赛中出现这样的题，那简直就是坑爹。

其中为了更容易检查错误，采取了一些对齐。和变量的命名修改，和hdu3911有些区别，

在做hdu3911吃了亏.....

代码：

#include
      
       #define HH 1#define ZERO 2#define ONE 3struct st{    int l,r;    int lnum,rnum;    int one_lmax,one_rmax,one_max;    int zer_lmax,zer_rmax,zer_max;    int color;    int sum;}f[100002*4];int date[100002];int max(int x,int y){    if(x>y)        return x;    else return y;}int min(int x,int y){    if(x
       
        lnum=lll->lnum;    fa->rnum=rrr->rnum;    fa->sum=lll->sum+rrr->sum;    if(lll->rnum==0&&rrr->lnum==0)    {        fa->zer_lmax=(lll->zer_lmax==(lll->r-lll->l+1))? lll->zer_lmax+rrr->zer_lmax:lll->zer_lmax;        fa->zer_rmax=(rrr->zer_rmax==(rrr->r-rrr->l+1))? rrr->zer_rmax+lll->zer_rmax:rrr->zer_rmax;        fa->zer_max =Max(max(fa->zer_lmax,fa->zer_rmax),max(lll->zer_max,rrr->zer_max),lll->zer_rmax+rrr->zer_lmax);    }    else     {        fa->zer_lmax=lll->zer_lmax;        fa->zer_rmax=rrr->zer_rmax;        fa->zer_max =max(lll->zer_max,rrr->zer_max);    }    if(lll->rnum==1&&rrr->lnum==1)    {        fa->one_lmax=(lll->one_lmax==(lll->r-lll->l+1))? lll->one_lmax+rrr->one_lmax:lll->one_lmax;        fa->one_rmax=(rrr->one_rmax==(rrr->r-rrr->l+1))? rrr->one_rmax+lll->one_rmax:rrr->one_rmax;        fa->one_max =Max(max(fa->one_lmax,fa->one_rmax),max(lll->one_max,rrr->one_max),lll->one_rmax+rrr->one_lmax);    }    else     {        fa->one_lmax=lll->one_lmax;        fa->one_rmax=rrr->one_rmax;        fa->one_max =max(lll->one_max,rrr->one_max);    }}void down(int n){    int k;    if(f[n].color==ONE)    {        f[n*2].color=f[n].color;        f[n*2].lnum =1;        f[n*2].rnum =1;        f[n*2].one_lmax=f[n*2].r-f[n*2].l+1;        f[n*2].one_rmax=f[n*2].r-f[n*2].l+1;        f[n*2].one_max =f[n*2].r-f[n*2].l+1;        f[n*2].zer_lmax=0;        f[n*2].zer_rmax=0;        f[n*2].zer_max =0;        f[n*2].sum=f[n*2].r-f[n*2].l+1;        f[n*2+1].color=f[n].color;        f[n*2+1].lnum =1;        f[n*2+1].rnum =1;        f[n*2+1].one_lmax=f[n*2+1].r-f[n*2+1].l+1;        f[n*2+1].one_rmax=f[n*2+1].r-f[n*2+1].l+1;        f[n*2+1].one_max =f[n*2+1].r-f[n*2+1].l+1;        f[n*2+1].zer_lmax=0;        f[n*2+1].zer_rmax=0;        f[n*2+1].zer_max =0;        f[n*2+1].sum=f[n*2+1].r-f[n*2+1].l+1;        f[n].color=0;    }    else if(f[n].color==ZERO)    {        f[n*2].color=f[n].color;        f[n*2].lnum=0;        f[n*2].rnum=0;        f[n*2].one_lmax=0;        f[n*2].one_max =0;        f[n*2].one_rmax=0;        f[n*2].zer_lmax=f[n*2].r-f[n*2].l+1;        f[n*2].zer_rmax=f[n*2].r-f[n*2].l+1;        f[n*2].zer_max =f[n*2].r-f[n*2].l+1;        f[n*2].sum=0;        f[n*2+1].color=f[n].color;        f[n*2+1].lnum=0;        f[n*2+1].rnum=0;        f[n*2+1].one_lmax=0;        f[n*2+1].one_rmax=0;        f[n*2+1].one_max =0;        f[n*2+1].zer_lmax=f[n*2+1].r-f[n*2+1].l+1;        f[n*2+1].zer_rmax=f[n*2+1].r-f[n*2+1].l+1;        f[n*2+1].zer_max =f[n*2+1].r-f[n*2+1].l+1;        f[n*2+1].sum=0;        f[n].color=0;    }    else if(f[n].color==HH)    {        if(f[n*2].color==ONE)            f[n*2].color=ZERO;        else if(f[n*2].color==ZERO)            f[n*2].color=ONE;        else if(f[n*2].color==0)            f[n*2].color=HH;        else if(f[n*2].color==HH)            f[n*2].color=0;        if(f[n*2].lnum==0)            f[n*2].lnum=1;        else f[n*2].lnum=0;        if(f[n*2].rnum==0)            f[n*2].rnum=1;        else f[n*2].rnum=0;        if(f[n*2+1].color==ONE)            f[n*2+1].color=ZERO;        else if(f[n*2+1].color==ZERO)            f[n*2+1].color=ONE;        else if(f[n*2+1].color==0)            f[n*2+1].color=HH;        else if(f[n*2+1].color==HH)            f[n*2+1].color=0;        if(f[n*2+1].lnum==0)            f[n*2+1].lnum=1;        else f[n*2+1].lnum=0;        if(f[n*2+1].rnum==0)            f[n*2+1].rnum=1;        else f[n*2+1].rnum=0;        k=f[n*2].one_lmax;        f[n*2].one_lmax=f[n*2].zer_lmax;        f[n*2].zer_lmax=k;        k=f[n*2].one_max;        f[n*2].one_max=f[n*2].zer_max;        f[n*2].zer_max=k;        k=f[n*2].one_rmax;        f[n*2].one_rmax=f[n*2].zer_rmax;        f[n*2].zer_rmax=k;        f[n*2].sum=f[n*2].r-f[n*2].l+1-f[n*2].sum;        k=f[n*2+1].one_lmax;        f[n*2+1].one_lmax=f[n*2+1].zer_lmax;        f[n*2+1].zer_lmax=k;        k=f[n*2+1].one_max;        f[n*2+1].one_max=f[n*2+1].zer_max;        f[n*2+1].zer_max=k;        k=f[n*2+1].one_rmax;        f[n*2+1].one_rmax=f[n*2+1].zer_rmax;        f[n*2+1].zer_rmax=k;        f[n*2+1].sum=f[n*2+1].r-f[n*2+1].l+1-f[n*2+1].sum;        f[n].color=0;    }}void build(int l,int r,int n){    int mid=(l+r)/2;    f[n].l=l;    f[n].r=r;    f[n].color=0;    if(l==r)    {        f[n].lnum=date[l];        f[n].rnum=date[l];        if(date[l]==0)        {            f[n].zer_lmax=1;            f[n].zer_rmax=1;            f[n].zer_max=1;            f[n].one_lmax=0;            f[n].one_rmax=0;            f[n].one_max=0;            f[n].sum=0;        }        else if(date[l]==1)        {            f[n].zer_lmax=0;            f[n].zer_rmax=0;            f[n].zer_max=0;            f[n].one_lmax=1;            f[n].one_max=1;            f[n].one_rmax=1;            f[n].sum=1;        }        return;    }    build(l,mid,n*2);    build(mid+1,r,n*2+1);    up(&f[n],&f[n*2],&f[n*2+1]);}void xx(int n,int x){        int k;        if(x==0)        {            f[n].lnum=0;            f[n].rnum=0;            f[n].color=ZERO;            f[n].one_lmax=0;            f[n].one_rmax=0;            f[n].one_max =0;            f[n].zer_lmax=f[n].r-f[n].l+1;            f[n].zer_max =f[n].r-f[n].l+1;            f[n].zer_rmax=f[n].r-f[n].l+1;            f[n].sum=0;        }        else if(x==1)        {            f[n].lnum=1;            f[n].rnum=1;            f[n].color=ONE;            f[n].one_lmax=f[n].r-f[n].l+1;            f[n].one_rmax=f[n].r-f[n].l+1;            f[n].one_max =f[n].r-f[n].l+1;            f[n].zer_lmax=0;            f[n].zer_rmax=0;            f[n].zer_max =0;            f[n].sum=f[n].r-f[n].l+1;        }        else if(x==2)        {            if(f[n].color==HH)            {                f[n].color=0;                f[n].sum=f[n].r-f[n].l+1-f[n].sum;            }            else if(f[n].color==ONE)            {                f[n].color=ZERO;                f[n].sum=0;            }            else if(f[n].color==ZERO)            {                f[n].color=ONE;                f[n].sum=f[n].r-f[n].l+1;            }            else if(f[n].color==0)            {                f[n].color=HH;                f[n].sum=f[n].r-f[n].l+1-f[n].sum;            }            if(f[n].lnum==1)                f[n].lnum=0;            else f[n].lnum=1;            if(f[n].rnum==1)                f[n].rnum=0;            else f[n].rnum=1;            k=f[n].one_lmax;            f[n].one_lmax=f[n].zer_lmax;            f[n].zer_lmax=k;            k=f[n].one_max;            f[n].one_max=f[n].zer_max;            f[n].zer_max=k;            k=f[n].one_rmax;            f[n].one_rmax=f[n].zer_rmax;            f[n].zer_rmax=k;        }}void update(int l,int r,int n,int x){    int mid=(f[n].l+f[n].r)/2;    if(f[n].l==l&&f[n].r==r)    {        xx(n,x);        return ;    }    if(f[n].color!=0)        down(n);    if(mid>=r)        update(l,r,n*2,x);    else if(mid
        
         =r)        return query(l,r,n*2,x);    else if(mid
         
          0)    {        while(t--)        {            scanf("%d%d",&n,&m);            for(i=1;i<=n;i++)                scanf("%d",&date[i]);            build(1,n,1);            while(m--)            {                scanf("%d%d%d",&x,&l,&r);                l++,r++;                if(x==0||x==1||x==2)                {                    update(l,r,1,x);                }                else if(x==3||x==4)                {                    k=query(l,r,1,x);                    printf("%d\n",k);                }            }        }    }    return 0;}