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.

 

Output

For each output operation , output the result.

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define SD(x,y) scanf("%lf%lf",&x,&y)

#define P_ printf(" ")

#define ll root<<1

#define rr root<<1|1

#define lson ll,l,mid

#define rson rr,mid+1,r

typedef long long LL;

const int MAXN=;

struct Node{

    int len,n0,ln0,rn0,sum,v,lazy,x_or;

    int n1,ln1,rn1;

    Node init(){

        SI(v);

        n0=ln0=rn0=(v==);

        n1=ln1=rn1=(v==);

        sum=v;

    }

};

Node tree[MAXN<<];

void XOR(int root,int v){

    swap(tree[root].n0,tree[root].n1);

    swap(tree[root].ln0,tree[root].ln1);

    swap(tree[root].rn0,tree[root].rn1);

    tree[root].sum=v-tree[root].sum;

    if(tree[root].lazy!=-)tree[root].lazy^=;

    //printf("%d %d %d %d %d %d\n",tree[root].n0,tree[root].ln0,tree[root].rn0,tree[root].n1,tree[root].ln1,tree[root].rn1);

}

void pushup(int root){

    tree[root].sum=tree[ll].sum+tree[rr].sum;

    tree[root].ln0=tree[ll].ln0;

    tree[root].rn0=tree[rr].rn0;

    if(tree[ll].ln0==tree[ll].len)tree[root].ln0+=tree[rr].ln0;

    if(tree[rr].rn0==tree[rr].len)tree[root].rn0+=tree[ll].rn0;

    tree[root].n0=max(max(tree[root].ln0,tree[root].rn0),tree[ll].rn0+tree[rr].ln0);

    tree[root].ln1=tree[ll].ln1;

    tree[root].rn1=tree[rr].rn1;

    if(tree[ll].ln1==tree[ll].len)tree[root].ln1+=tree[rr].ln1;

    if(tree[rr].rn1==tree[rr].len)tree[root].rn1+=tree[ll].rn1;

    tree[root].n1=max(max(tree[root].ln1,tree[root].rn1),tree[ll].rn1+tree[rr].ln1);

}

void pushdown(int root,int v){

    if(tree[root].lazy!=-){

        tree[ll].lazy=tree[rr].lazy=tree[root].lazy;

        tree[ll].ln0=tree[ll].n0=tree[ll].rn0=tree[root].lazy?:tree[ll].len;

        tree[rr].ln0=tree[rr].n0=tree[rr].rn0=tree[root].lazy?:tree[rr].len;

        tree[rr].ln1=tree[rr].n1=tree[rr].rn1=tree[root].lazy?tree[rr].len:;

        tree[ll].ln1=tree[ll].n1=tree[ll].rn1=tree[root].lazy?tree[ll].len:;

        tree[ll].sum=tree[root].lazy?tree[ll].len:;

        tree[rr].sum=tree[root].lazy?tree[rr].len:;

        /*

        tree[root].sum=v;

        tree[root].ln0=tree[root].rn0=tree[root].lazy?0:tree[root].len;

        tree[root].ln1=tree[root].rn1=tree[root].lazy?tree[root].len:0;

        */

        tree[ll].x_or=tree[rr].x_or=;

        tree[root].lazy=-;

    }

    if(tree[root].x_or){

        tree[ll].x_or^=;

        tree[rr].x_or^=;

        XOR(ll,tree[ll].len);

        XOR(rr,tree[rr].len);

        tree[root].x_or=;

    }

}

void build(int root,int l,int r){

    tree[root].len=r-l+;

    tree[root].lazy=-;

    tree[root].x_or=;

    if(l==r){

        tree[root].init();return;

    }

    int mid=(l+r)>>;

    build(lson);build(rson);

    pushup(root);

}

void update(int root,int l,int r,int A,int B,int c){

    int mid=(l+r)>>;

    pushdown(root,tree[root].len);

    if(l>=A&&r<=B){

        //printf("c=%d\n",c);

        if(c<){

            tree[root].lazy=c;

            tree[root].sum=tree[root].lazy?tree[root].len:;

        tree[root].n0=tree[root].ln0=tree[root].rn0=tree[root].lazy?:tree[root].len;

        tree[root].n1=tree[root].ln1=tree[root].rn1=tree[root].lazy?tree[root].len:;

        }

        else{

             tree[root].x_or=;

            XOR(root,tree[root].len);

        }

        return;

    }

    pushdown(root,r-l+);

    if(mid>=A)update(lson,A,B,c);

    if(mid<B)update(rson,A,B,c);

    pushup(root);

}

int query(int root,int l,int r,int A,int B,int c){

    if(l>=A&&r<=B){

    //    printf("%d %d\n",tree[root].sum,tree[root].n1);

        if(c==)return tree[root].sum;

        else return tree[root].n1;

    }

    pushdown(root,r-l+);

    int mid=(l+r)>>;

    if(mid>=B)return query(lson,A,B,c);

    else if(mid<A)return query(rson,A,B,c);

    else{

        int ans1=query(lson,A,mid,c);

        int ans2=query(rson,mid+,B,c);

        if(c==)return ans1+ans2;

        else return max(max(ans1,ans2),min(mid-A+,tree[ll].rn1)+min(B-mid,tree[rr].ln1));

    }

}

int main(){

    int T,N,M;

    SI(T);

    while(T--){

        SI(N);SI(M);

        build(,,N-);

    while(M--){

            int p,a,b;

        scanf("%d%d%d",&p,&a,&b);

        if(p<=)update(,,N-,a,b,p);

        else{

            printf("%d\n",query(,,N-,a,b,p));

        }

        }

    }

    return ;

}