题目描述

$lxhgww$最近收到了一个$01$序列,序列里面包含了$n$个数。

现在对于这个序列有五种变换操作和询问操作:

$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$。

对于每一种询问操作,$lxhgww$都需要给出回答,聪明的程序员们,你们能帮助他吗?

输入格式

输入数据第一行包括$2$个数,$n$和$m$,分别表示序列的长度和操作数目。

第二行包括$n$个数,表示序列的初始状态。

接下来$m$行,每行$3$个数,$op, a, b$,表示对于区间$[a, b]$执行标号为$op$的操作

输出格式

对于每一个询问操作,输出一行,包括$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

数据范围

对于$30\%$的数据,$1\leq n, m\leq 1000$。

对于100%的数据,$1\leq n, m \leq 100000$

菜鸡的咆哮

这道毒瘤的线段树差点让我猝死在晚自习上$QAQ$。

思维难度不是很大,但代码写起来确实恼火。

维护变量

对于询问区间有多少个$1$,维护$sum[k]$。

对于询问区间有多少连续的$1$,维护$suml \_1[k],sumr \_1[k],sum \_1[k]$。

分别代表区间左端开始,右端开始,整个区间连续的$1$的个数。

对于区间异或操作,还要维护$suml \_0[k],sumr \_0[k],sum \_0[k]$,含义同上。

因为是区间修改,还要维护三个$lazy\ tage$。

$push\_up$

假定当前区间编号为$k$,左右端点分别为$a[k],b[k]$。

左端连续$1$维护分两种情况。

当左儿子区间全为$1$时:

爸爸区间左端连续$1$长度=左儿子区间长+右儿子区间左端连续$1$长度。

否则=左儿子区间左端连续$1$长度。

if(maxl_1[ls(k)]==b[ls(k)]-a[ls(k)]+1)
    maxl_1[k]=maxl_1[ls(k)]+maxl_1[rs(k)];
else maxl_1[k]=maxl_1[ls(k)];

右端连续$1$同理。

if(maxr_1[rs(k)]==b[rs(k)]-a[rs(k)]+1)
    maxr_1[k]=maxr_1[rs(k)]+maxr_1[ls(k)];
else maxr_1[k]=maxr_1[rs(k)];

最长连续$1$分$3$种情况:

左儿子连续$1$数量,右儿子连续$1$数量,左儿子右端连续$1$$+$右儿子左端连续$1$。

max_1[k]=max(max(max_1[ls(k)],max_1[rs(k)]),maxr_1[ls(k)]+maxl_1[rs(k)]);

$0$的处理同理。

$1$的数量:学过线段树都会吧.......

$push\_down$

三个标记,铺平标记优先级一定大于异或标记。

(先翻转再铺平等价于直接铺平)

所以优先考虑铺平标记,在下传了铺平标记后将子节点异或标记清零。

下传异或标记后将子节点异或标记进行异或。

因为铺平标记总是被优先考虑所以不用管子节点的铺平标记。

铺平为$1$:有关$1$的变为该区间长度,$0$的变为$0$。

铺平为$0$:有关$0$的变为该区间长度,$1$的变为$0$。

异或:将有关$0$的与有关$1$的交换。

查询答案

注意一点:

如果没有进入某个区间(不在查询范围内),要返回$(data)\{0,0,0\}$并标记。

在将答案向上传递时:

若左儿子不在查询范围内,爸爸节点左端最大连续$1$=右儿子左端最大连续$1$。

若右儿子不在查询范围内,爸爸节点右端最大连续$1$=左儿子右端最大连续$1$。

其他两种情况与$push\_up$相同。

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
int num[maxn];
int a[4*maxn];
int b[4*maxn];
int sum[4*maxn];
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
int maxl_1[4*maxn],maxl_0[4*maxn];
int maxr_1[4*maxn],maxr_0[4*maxn];
int max_1[4*maxn],max_0[4*maxn];
int sign_1[4*maxn],sign_0[4*maxn],sign_xor[4*maxn];

void push_up(int k){
    //左儿子区间全为1 
    if(maxl_1[ls(k)]==b[ls(k)]-a[ls(k)]+1)
        maxl_1[k]=maxl_1[ls(k)]+maxl_1[rs(k)];
    else maxl_1[k]=maxl_1[ls(k)];
    //右儿子区间全为1 
    if(maxr_1[rs(k)]==b[rs(k)]-a[rs(k)]+1)
        maxr_1[k]=maxr_1[rs(k)]+maxr_1[ls(k)];
    else maxr_1[k]=maxr_1[rs(k)];    
    //最长连续1的三种情况
    max_1[k]=max(max(max_1[ls(k)],max_1[rs(k)]),maxr_1[ls(k)]+maxl_1[rs(k)]);

    //左儿子区间全为0 
    if(maxl_0[ls(k)]==b[ls(k)]-a[ls(k)]+1)
        maxl_0[k]=maxl_0[ls(k)]+maxl_0[rs(k)];
    else maxl_0[k]=maxl_0[ls(k)];
    //右儿子区间全为0 
    if(maxr_0[rs(k)]==b[rs(k)]-a[rs(k)]+1)
        maxr_0[k]=maxr_0[rs(k)]+maxr_0[ls(k)];
    else maxr_0[k]=maxr_0[rs(k)];    
    //最长连续0的三种情况
    max_0[k]=max(max(max_0[ls(k)],max_0[rs(k)]),maxr_0[ls(k)]+maxl_0[rs(k)]);

    sum[k]=sum[ls(k)]+sum[rs(k)];
}

//巴啦啦能量 区间变1 
void update_1(int k){
    sum[k]=maxl_1[k]=maxr_1[k]=max_1[k]=b[k]-a[k]+1;
    maxl_0[k]=maxr_0[k]=max_0[k]=0;
    sign_1[k]=1;
    sign_xor[k]=sign_0[k]=0;
}
//巴啦啦能量 区间变0 
void update_0(int k){
    sum[k]=maxl_1[k]=maxr_1[k]=max_1[k]=0;
    maxl_0[k]=maxr_0[k]=max_0[k]=b[k]-a[k]+1;
    sign_0[k]=1;
    sign_xor[k]=sign_1[k]=0;
}
//巴啦啦能量 区间异或 
void update_xor(int k){
    sum[k]=b[k]-a[k]+1-sum[k];
    swap(max_1[k],max_0[k]);
    swap(maxl_1[k],maxl_0[k]);
    swap(maxr_1[k],maxr_0[k]);
    sign_xor[k]^=1;
}
void push_down(int k){
    if(sign_1[k]){
        update_1(ls(k));
        update_1(rs(k));
        sign_1[k]=0;
    }
    if(sign_0[k]){
        update_0(ls(k));
        update_0(rs(k));
        sign_0[k]=0;
    }
    if(sign_xor[k]){
        update_xor(ls(k));
        update_xor(rs(k));
        sign_xor[k]=0;
    }
}
void build(int k,int l,int r){
    a[k]=l;b[k]=r;
    if(l==r){
        sum[k]=max_1[k]=maxl_1[k]=maxr_1[k]=num[l];
        max_0[k]=maxl_0[k]=maxr_0[k]=num[l]^1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    push_up(k);
}
int ask_sum(int k,int x,int y){
    int ans=0;
    if(a[k]>=x&&b[k]<=y) return sum[k];
    int mid=(a[k]+b[k])>>1;
    push_down(k);
    if(x<=mid) ans+=ask_sum(ls(k),x,y);
    if(y>mid) ans+=ask_sum(rs(k),x,y);
    return ans;
}
struct data{
    int l,r,t;
};
data ask_max(int k,int x,int y){
    if(a[k]>=x&&b[k]<=y) return (data){maxl_1[k],maxr_1[k],max_1[k]};
    int mid=(a[k]+b[k])>>1;
    push_down(k);
    data now,xl,xr;
    int isl=0,isr=0;
    if(x<=mid) xl=ask_max(ls(k),x,y);
    else{xl=(data){0,0,0},isl=1;}
    if(y>mid) xr=ask_max(rs(k),x,y);
    else{xr=(data){0,0,0},isr=1;}
    
    if(xl.l==b[ls(k)]-a[ls(k)]+1) now.l=xl.l+xr.l;
    else if(isl==1) now.l=xr.l;
    else now.l=xl.l;
    if(xr.r==b[rs(k)]-a[rs(k)]+1) now.r=xr.r+xl.r;
    else if(isr==1) now.r=xl.r;
    else now.r=xr.r;
    now.t=max(max(xl.t,xr.t),xl.r+xr.l);
    return now;
}
// 0变0 1变1 2异或 
void upd(int k,int x,int y,int pos){
    if(a[k]>=x&&b[k]<=y){
        if(pos==0) update_0(k);
        if(pos==1) update_1(k);
        if(pos==2) update_xor(k);
        return;
    }
    int mid=(a[k]+b[k])>>1;
    push_down(k);
    if(x<=mid) upd(ls(k),x,y,pos);
    if(y>mid) upd(rs(k),x,y,pos);
    push_up(k);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    }
    build(1,1,n);
    int opt,x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&opt,&x,&y);
        x++;y++;
        if(opt==0) upd(1,x,y,0);
        if(opt==1) upd(1,x,y,1);
        if(opt==2) upd(1,x,y,2);
        if(opt==3) printf("%d\n",ask_sum(1,x,y));
        if(opt==4) printf("%d\n",ask_max(1,x,y).t);
    }
    return 0;
}