操作

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]

不太熟悉异或操作

用两种标记 col表示 区间变成0/1  。 ox表示 区间异或

0 1 操作跟普通线段树一样

异或操作须要 ox[rt]^=1;

......搞了一个晚上 错这里了..

4 操作普通的区间合并啦

lsum记录左边開始连续的1的个数 rsum记录右边開始连续的1的个数

zero就记录连续的0啦

还有在延迟的时候须要先pushdown   col标记  再 pushdown ox标记

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#include <queue>

#include <stack>

#include <vector>

#include <deque>

#include <set>

#include <map>

#define IN     freopen ("in.txt" , "r" , stdin);

#define OUT  freopen ("out.txt" , "w" , stdout);

typedef long long  LL;

const int MAXN = 100110;//点数的最大值

const int MAXM = 20006;//边数的最大值

const int INF = 11521204;

const int mod=1000000007;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int num1[MAXN<<2],num2[MAXN<<2],ans[MAXN];

int sum[MAXN<<2],lsum[MAXN<<2],rsum[MAXN<<2];

int zero[MAXN<<2],lzero[MAXN<<2],rzero[MAXN<<2];

int col[MAXN<<2],ox[MAXN<<2];

void pushup(int rt,int m)

{

    int lx=m-(m>>1);

    int rx=(m>>1);

    //1的向上更新

    lsum[rt]=lsum[rt<<1];

    rsum[rt]=rsum[rt<<1|1];

    if(lsum[rt]==lx)  lsum[rt]+=lsum[rt<<1|1];

    if(rsum[rt]==rx)  rsum[rt]+=rsum[rt<<1];

    sum[rt]=max(max(sum[rt<<1],sum[rt<<1|1]),rsum[rt<<1]+lsum[rt<<1|1]);

    //0的向上更新

    lzero[rt]=lzero[rt<<1];

    rzero[rt]=rzero[rt<<1|1];

    if(lzero[rt]==lx)  lzero[rt]+=lzero[rt<<1|1];

    if(rzero[rt]==rx)  rzero[rt]+=rzero[rt<<1];

    zero[rt]=max(max(zero[rt<<1],zero[rt<<1|1]),rzero[rt<<1]+lzero[rt<<1|1]);

    //总数的更新

    num1[rt]=num1[rt<<1]+num1[rt<<1|1];

    num2[rt]=num2[rt<<1]+num2[rt<<1|1];

}

void pushdown(int rt,int m,int l,int r)

{

    if(col[rt]!=-1)

    {

        ox[rt<<1]=ox[rt<<1|1]=0;

        col[rt<<1]=col[rt<<1|1]=col[rt];

        sum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=col[rt]?m-(m>>1):0;

        sum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=col[rt]?m>>1:0;

        zero[rt<<1]=lzero[rt<<1]=rzero[rt<<1]=col[rt]?0:m-(m>>1);

        zero[rt<<1|1]=lzero[rt<<1|1]=rzero[rt<<1|1]=col[rt]?0:m>>1;

        num1[rt<<1]=col[rt]? m-(m>>1):0;

        num2[rt<<1]=col[rt]?0:m-(m>>1);

        num1[rt<<1|1]=col[rt]?m>>1:0;

        num2[rt<<1|1]=col[rt]?

0:m>>1;

        col[rt]=-1;

    }

    if(ox[rt])

    {

        ox[rt<<1]^=1;

        ox[rt<<1|1]^=1;

        swap(sum[rt<<1],zero[rt<<1]);

        swap(sum[rt<<1|1],zero[rt<<1|1]);

        swap(lsum[rt<<1],lzero[rt<<1]);

        swap(lsum[rt<<1|1],lzero[rt<<1|1]);

        swap(rsum[rt<<1],rzero[rt<<1]);

        swap(rsum[rt<<1|1],rzero[rt<<1|1]);

        swap(num1[rt<<1],num2[rt<<1]);

        swap(num1[rt<<1|1],num2[rt<<1|1]);

        ox[rt]=0;

    }

}

void build(int l,int r,int rt)

{

    col[rt]=-1;

    ox[rt]=0;

    if(l==r)

    {

        scanf("%d",&num1[rt]);

        if(num1[rt])

        {

            num2[rt]=0;

            sum[rt]=lsum[rt]=rsum[rt]=1;

            zero[rt]=lzero[rt]=rzero[rt]=0;

        }

        else

        {

            sum[rt]=lsum[rt]=rsum[rt]=0;

            zero[rt]=lzero[rt]=rzero[rt]=1;

            num2[rt]=1;

        }

        return ;

    }

    int m=(l+r)>>1;

    build(lson);

    build(rson);

    pushup(rt,r-l+1);

}

void update(int L,int R,int c,int l,int r,int rt)//更新  0 1 2 分别表示区间更新为0 , 1。异或

{

    if(L<=l&&r<=R)

    {

        if(c==2)//异或

        {

            swap(num1[rt],num2[rt]);//0 1 个数交换

            swap(sum[rt],zero[rt]);

            swap(lsum[rt],lzero[rt]);

            swap(rsum[rt],rzero[rt]);

            ox[rt]^=1;

        }

        else

        {

            sum[rt]=lsum[rt]=rsum[rt]=c==1?r-l+1:0;

            zero[rt]=lzero[rt]=rzero[rt]=c==1?

0:r-l+1;

            num1[rt]=c==1?r-l+1:0;

            num2[rt]=c==1?0:r-l+1;

            col[rt]=c;

            ox[rt]=0;

        }

        return ;

    }

    int m=(l+r)>>1;

    pushdown(rt,r-l+1,l,r);

    if(L<=m)    update(L,R,c,lson);

    if(m<R)      update(L,R,c,rson);

    pushup(rt,r-l+1);

}

int query1(int L,int R,int l,int r,int rt)//输出1的个数

{

    if(L<=l&&r<=R)

    {

        return num1[rt];

    }

    int m=(l+r)>>1,res=0;

    pushdown(rt,r-l+1,l,r);

    if(L<=m)    res+=query1(L,R,lson);

    if(m<R)    res+=query1(L,R,rson);

    return res;

}

int query2(int L,int R,int l,int r,int rt)//输出连续的

{

    if(L<=l&&r<=R)

    {

        return sum[rt];

    }

    int m=(l+r)>>1,res=0;

    pushdown(rt,r-l+1,l,r);

    if(L<=m)    res=max(res, query2(L,R,lson));

    if(m<R)    res=max(res,query2(L,R,rson));

    res = max(res, min(m-L+1, rsum[rt<<1])+min(R-m, lsum[rt<<1|1]));

    return res;

}

int main()

{

    int n,m,t;

   //IN;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        build(1,n,1);

        while(m--)

        {

            int a,b,c;

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

            a++,b++;

            if(c <=2)

                update(a,b,c,1,n,1);

            else

            {

                if(c==3)

                    printf("%d\n",query1(a,b,1,n,1));

                else printf("%d\n",query2(a,b,1,n,1));

            }

        }

    }

    return 0;

}

/*

1

4 3

0 0 1 1

1 1 2

2 1 2

3 1 1

*/