参考 http://dnizna.javaeye.com/blog/657622 的 写法

/*
    题意：长度为N的01串，Q个操作
    0 a b 将[a,b]置0
    1 a b 将[a,b]置1
    2 a b 将[a,b]内的数翻转，0->1 1->0
    3 a b 查询[a,b]内1的个数
    4 a b 查询[a,b]内最多的连续1个数

    维护max1,maxL1,maxR1 最多连续1的个数，左边最多连续1的个数，右边最多连续1的个数
    
    需要延迟标记 set rev
    set = 1 表示置为1
    set = 0 表示置为0
    set = -1 表示没有置数
    rev = 1表示需要翻转

    所以在需要修改时，遇到整段修改的，将该段的值更新为正确的
    如set 1 的话 sum = right - left +1
    然后对于其儿子的，不用更新！直接在该段标记set = 1 表示以后孩子需要更新，但该段已经是正确的值！！！
    
    标记的做法主要就是上面说的了，某一段是正确的，但标记其儿子等都需要修改
    每次遇到一条线段时，push_down() ，这样子实现了延迟更新了

    如果set = 1,rev = 1这样子并不表明是先set，还是先reverse，就这里的细节了！！

    但如果要set的话，必定不需再reverse了
    所以在某一段，如果其需要set，更新孩子，将该标记传给孩子，表明孩子的孩子以后需要更新
    同时，将孩子的rev = 0
    即： rev + set -> set
          set + rev -> set + rev
    所以push_down()那里的处理顺序是：
    if(set)
    if(rev)
    两者是并列的！！

    考虑例子：
    [0     4]
    [0 2]
    先将[0,2]标记(set or rev)，接下来是标记[0,4]，上面的覆盖下面了
    所以为set的话，[0,2]的rev置为0了  rev的话，就传下去
    所以push_down()的if 是并列的
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 100010;

int x[MAXN];

struct Node
{
    int max0,maxL0,maxR0;
    int max1,maxL1,maxR1;
    int sum,set,rev;    
};

struct SegTree
{
    Node nodes[MAXN*3];

    void update(int p,int left,int right)
    {
        if(left == right)return;
        nodes[p].sum = nodes[2*p].sum + nodes[2*p+1].sum;

        int mid = (left+right)>>1;

        nodes[p].maxL0 = nodes[2*p].maxL0;
        if(nodes[p].maxL0 == mid-left+1)nodes[p].maxL0 += nodes[2*p+1].maxL0;
        nodes[p].maxR0 = nodes[2*p+1].maxR0;
        if(nodes[p].maxR0 == right-mid)nodes[p].maxR0 += nodes[2*p].maxR0;
        nodes[p].max0 = max(nodes[2*p].max0,nodes[2*p+1].max0);
        nodes[p].max0 = max(nodes[p].max0,nodes[2*p].maxR0+nodes[2*p+1].maxL0);

        nodes[p].maxL1 = nodes[2*p].maxL1;
        if(nodes[p].maxL1 == mid-left+1)nodes[p].maxL1 += nodes[2*p+1].maxL1;
        nodes[p].maxR1 = nodes[2*p+1].maxR1;
        if(nodes[p].maxR1 == right-mid)nodes[p].maxR1 += nodes[2*p].maxR1;
        nodes[p].max1 = max(nodes[2*p].max1,nodes[2*p+1].max1);
        nodes[p].max1 = max(nodes[p].max1,nodes[2*p].maxR1+nodes[2*p+1].maxL1);
    }
    
    void push_down(int p,int left,int right)
    {
        if(left == right)return;
        int mid = (left+right)>>1;
        //set  与  rev  是并列的！！！
        if(nodes[p].set != -1)
        {
            int val = nodes[p].set;
            nodes[p].set = -1;
            nodes[2*p].set = nodes[2*p+1].set = val;
            nodes[2*p].rev = nodes[2*p+1].rev = 0;//将孩子的rev置为0
        
            nodes[2*p].sum = val==1?mid-left+1:0;
            nodes[2*p].max0 = nodes[2*p].maxL0 = nodes[2*p].maxR0 = val==0?mid-left+1:0;
            nodes[2*p].max1 = nodes[2*p].maxL1 = nodes[2*p].maxR1 = val==1?mid-left+1:0;

            nodes[2*p+1].sum = val==1?right-mid:0;
            nodes[2*p+1].max0 = nodes[2*p+1].maxL0 = nodes[2*p+1].maxR0 = val==0?right-mid:0;
            nodes[2*p+1].max1 = nodes[2*p+1].maxL1 = nodes[2*p+1].maxR1 = val==1?right-mid:0;
        }
        if(nodes[p].rev)
        {
            nodes[p].rev = false;
            nodes[2*p].rev ^= 1;//这里是翻转！！！
            nodes[2*p+1].rev ^= 1;
            
            nodes[2*p].sum = mid-left+1 - nodes[2*p].sum;
            swap(nodes[2*p].max0,nodes[2*p].max1);
            swap(nodes[2*p].maxL0,nodes[2*p].maxL1);
            swap(nodes[2*p].maxR0,nodes[2*p].maxR1);

            nodes[2*p+1].sum = right - mid - nodes[2*p+1].sum;
            swap(nodes[2*p+1].max0,nodes[2*p+1].max1);
            swap(nodes[2*p+1].maxL0,nodes[2*p+1].maxL1);
            swap(nodes[2*p+1].maxR0,nodes[2*p+1].maxR1);
        }
    }

    void build(int p,int left,int right)
    {
        nodes[p].set = -1;
        nodes[p].rev = 0;
        if(left == right)
        {
            nodes[p].sum = x[left];
            nodes[p].max0 = nodes[p].maxL0 = nodes[p].maxR0 = (x[left]==0);
            nodes[p].max1 = nodes[p].maxL1 = nodes[p].maxR1 = (x[left]==1);
            return;
        }
        int mid = (left+right)>>1;
        build(2*p,left,mid);
        build(2*p+1,mid+1,right);
        update(p,left,right);
    }

    void change(int p,int left,int right,int l,int r,int op)
    {
        push_down(p,left,right);
        if(l<=left && right<=r)
        {
            if(op == 2)
            {
                nodes[p].rev = true;
                nodes[p].sum = right - left + 1 - nodes[p].sum;
                swap(nodes[p].max0,nodes[p].max1);
                swap(nodes[p].maxL0,nodes[p].maxL1);
                swap(nodes[p].maxR0,nodes[p].maxR1);                 
            }
            else 
            {
                nodes[p].set = op;
                nodes[p].sum = op==1?right-left+1:0;
                nodes[p].max0 = nodes[p].maxL0 = nodes[p].maxR0 = op==0?right-left+1:0;
                nodes[p].max1 = nodes[p].maxL1 = nodes[p].maxR1 = op==1?right-left+1:0;
            }
            return;
        }
        int mid = (left+right)    >>1;
        if(l>mid)change(2*p+1,mid+1,right,l,r,op);
        else if(r<=mid)change(2*p,left,mid,l,r,op);
        else 
        {
            change(2*p,left,mid,l,mid,op);
            change(2*p+1,mid+1,right,mid+1,r,op);
        }
        update(p,left,right);
    }

    int query(int p,int left,int right,int l,int r,int op)
    {
        push_down(p,left,right);
        if(l<=left && right<=r)
        {
            if(op==3)return nodes[p].sum;
            return nodes[p].max1;
        }
        int mid = (left+right)>>1;
        if(l>mid)return query(2*p+1,mid+1,right,l,r,op);
        if(r<=mid)return query(2*p,left,mid,l,r,op);        
        if(op==3)return query(2*p,left,mid,l,mid,op)+query(2*p+1,mid+1,right,mid+1,r,op);
        int ans = max(query(2*p,left,mid,l,mid,op),query(2*p+1,mid+1,right,mid+1,r,op));
        int L = min(nodes[2*p].maxR1,mid+1-l);
        int R = min(nodes[2*p+1].maxL1,r-mid);
        ans = max(ans,L+R);
        return ans;
    }
};

SegTree segTree;

int main()
{
#ifdef ONLINE_JUDGE
#else 
    freopen("in","r",stdin);
#endif
    int T;
    for(scanf("%d",&T);T--;)
    {
        int  N,Q;
        int q,a,b;
        scanf("%d%d",&N,&Q);
        for(int i=0;i<N;i++)
            scanf("%d",&x[i]);
        segTree.build(1,0,N-1);
        for(int i=0;i<Q;i++)
        {
            scanf("%d%d%d",&q,&a,&b);
            if(q<=2)segTree.change(1,0,N-1,a,b,q);
            else printf("%d\n",segTree.query(1,0,N-1,a,b,q));
        }
    }
    return 0;
}