学步园

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]

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.

For each output operation , output the result.

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

5
2
6
5
#include<stdio.h>
#define N 300000
struct node
{
    int lbw,rbw,b;//分别代表最左边和最右边长度的颜色，左右子节点是否要更新
    int llen,rlen,len1,len0;//最左长度，最右长度，当前段最大连续为1长度，和最大连续为0的长度
    int sum1,sum0;//当前段为1的个数，和为0的个数
}tree[3*N];
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void builde(int l,int r,int k)//初始化
{
    int m=(l+r)>>1;
    tree[k].b=0;
    tree[k].lbw=tree[k].rbw=0;
    tree[k].llen=tree[k].rlen=r-l+1;
    tree[k].sum0=tree[k].len0=r-l+1;
    tree[k].len1=tree[k].sum1=0;
    if(l==r) return ;
    builde(l,m,k<<1); builde(m+1,r,k<<1|1);
}
//------异或------
void xcheng(int &a,int &b)//交换
{
    int tem;
    tem=a;a=b;b=tem;
}
void XOR(int k)
{
    xcheng(tree[k].len0,tree[k].len1);
    xcheng(tree[k].sum0,tree[k].sum1);
    tree[k].lbw=!tree[k].lbw; tree[k].rbw=!tree[k].rbw;
}
//-------更新左右子树------
void chang_chil(int k)//父节点K的段只为0或1，更新左右子树
{
    tree[k<<1].b=tree[k<<1|1].b=1;
    tree[k<<1].lbw=tree[k<<1].rbw=tree[k].lbw;
    tree[k<<1|1].lbw=tree[k<<1|1].rbw=tree[k].rbw;
    tree[k<<1].sum0=tree[k<<1].len0=(tree[k].len0+1)/2;
    tree[k<<1].sum1=tree[k<<1].len1=(tree[k].len1+1)/2;
    tree[k<<1|1].sum0=tree[k<<1|1].len0=tree[k].len0-tree[k<<1].len0;
    tree[k<<1|1].sum1=tree[k<<1|1].len1=tree[k].len1-tree[k<<1].len1;
    tree[k<<1].llen=tree[k<<1].rlen=max(tree[k<<1].len0,tree[k<<1].len1);
    tree[k<<1|1].llen=tree[k<<1|1].rlen=max(tree[k<<1|1].len0,tree[k<<1|1].len1);
}
void chang_childe(int k)//更新左右子树
{
        if(!tree[k].len0||!tree[k].len1)//覆盖
            chang_chil(k);
        else//异或，父节点只要是0与1并存时，而根据父节点子树又须要更新，那么一定就是异或
        {
            if(tree[k<<1].b){
                if(!tree[k<<1].len0||!tree[k<<1].len1)
                    chang_chil(k<<1);
                else tree[k<<1].b=0;
            }
            else tree[k<<1].b=1;
            XOR(k<<1);
            if(tree[k<<1|1].b){
                if(!tree[k<<1|1].len0||!tree[k<<1|1].len1)
                    chang_chil(k<<1|1);
                else tree[k<<1|1].b=0;
            }
            else tree[k<<1|1].b=1;
            XOR(k<<1|1);
        }
        tree[k].b=0;
}
//--------根据左右子树设置父节点-------
void set(int l,int m,int r,int k)
{
    tree[k].lbw=tree[k<<1].lbw; tree[k].llen=tree[k<<1].llen;
    tree[k].rbw=tree[k<<1|1].rbw;tree[k].rlen=tree[k<<1|1].rlen;
    tree[k].sum0=tree[k<<1].sum0+tree[k<<1|1].sum0;
    tree[k].sum1=tree[k<<1].sum1+tree[k<<1|1].sum1;
    tree[k].len0=max(tree[k<<1].len0,tree[k<<1|1].len0);
    tree[k].len1=max(tree[k<<1].len1,tree[k<<1|1].len1);
    if(tree[k<<1].rbw==tree[k<<1|1].lbw)
    {
        if(tree[k].llen==m-l+1) tree[k].llen+=tree[k<<1|1].llen;
        if(tree[k].rlen==r-m) tree[k].rlen+=tree[k<<1].rlen;
        if(tree[k<<1].rbw)
         tree[k].len1=max(tree[k].len1,tree[k<<1].rlen+tree[k<<1|1].llen);
        else
        tree[k].len0=max(tree[k].len0,tree[k<<1].rlen+tree[k<<1|1].llen);
    }
}
void updata(int l,int r,int k,int op,int L,int R)
{
    int m=(l+r)>>1;
    if(tree[k].b&&l!=r)//子树须更新时
        chang_childe(k);
    if(L<=l&&r<=R)
    {
        tree[k].b=1;
       if(l==r) tree[k].b=0;
        if(op==0){
            tree[k].lbw=tree[k].rbw=0;
            tree[k].llen=tree[k].rlen=tree[k].len0=r-l+1;
            tree[k].len1=0;
            tree[k].sum0=r-l+1; tree[k].sum1=0;
        }
        if(op==1){
            tree[k].lbw=tree[k].rbw=1;
            tree[k].llen=tree[k].rlen=tree[k].len1=r-l+1;
            tree[k].len0=0;
            tree[k].sum0=0; tree[k].sum1=r-l+1;
        }
        if(op==2)
                XOR(k);
        return ;
    }
    if(L<=m) updata(l,m,k<<1,op,L,R);
    if(R>m) updata(m+1,r,k<<1|1,op,L,R);
    set(l,m,r,k);
}
//---------求出答案-------
int query(int l,int r,int k,int op,int L,int R)
{
    int m=(l+r)>>1;
    if(tree[k].b&&l!=r)
        chang_childe(k);
    if(L<=l&&r<=R)
    {
        if(op==3) return tree[k].sum1;
        else return tree[k].len1;
    }
    int ans;
    if(R<=m) return query(l,m,k<<1,op,L,R);
    else if(L>m) return query(m+1,r,k<<1|1,op,L,R);
    else
    {
        ans=query(l,m,k<<1,op,L,R);
        if(op==3) ans+=query(m+1,r,k<<1|1,op,L,R);
        else
        {
            ans=max(ans,query(m+1,r,k<<1|1,op,L,R));
            if(tree[k<<1|1].lbw&&tree[k<<1].rbw)//注意这里在段L~R内求连续1的最大长度很重要，不能越界
            ans=max(ans,min(tree[k<<1].rlen,m-L+1)+min(tree[k<<1|1].llen,R-m));
        }
        return ans;
    }
}
int main()
{
    int n,m,op,L,R,t,num,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        builde(1,n,1);
        for( i=1;i<=n;i++)
        {
            scanf("%d",&num);
            if(num)updata(1,n,1,1,i,i);
        }
        while(m--)
        {
            scanf("%d%d%d",&op,&L,&R);
            if(op<=2) updata(1,n,1,op,L+1,R+1);
            else printf("%d\n",query(1,n,1,op,L+1,R+1));
        }
    }
}