Fwio_ @ 2024-02-16 19:36:49
快调疯了
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int n , m;
int a[N];
struct node{
int l , r;
int one , zero;
int tagone , tagzero , rev;
int lmax0 , lmax1;
int rmax0 , rmax1;
int max0 , max1;
}tr[N << 2];
void update(node &root , node &L , node &R){
root.one = L.one + R.one;
root.zero = L.zero + R.zero;
root.lmax1 = ((L.zero == 0) ? (L.one + R.lmax1) : (L.lmax1));
root.lmax0 = ((L.one == 0) ? (L.zero + R.lmax0) : (L.lmax0));
root.rmax1 = ((R.zero == 0) ? (R.one + L.rmax1) : (R.rmax1));
root.rmax0 = ((R.one == 0) ? (R.zero + L.rmax0) : (R.rmax0));
root.max0 = max(max(L.lmax0 , R.rmax0) , L.rmax0 + R.lmax0);
root.max1 = max(max(L.lmax1 , R.rmax1) , L.rmax1 + R.lmax1);
}
void pushup(int u){
update(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}
void pushdown(int u){
if(tr[u].tagzero){
tr[u << 1].zero = tr[u << 1].lmax0 = tr[u << 1].rmax0 = tr[u << 1].max0 = (tr[u << 1].r - tr[u << 1].l + 1);
tr[u << 1].one = tr[u << 1].lmax1 = tr[u << 1].rmax1 = tr[u << 1].max1 = 0;
tr[u << 1 | 1].zero = tr[u << 1 | 1].lmax0 = tr[u << 1 | 1].rmax0 = tr[u << 1 | 1].max0 = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
tr[u << 1 | 1].one = tr[u << 1 | 1].lmax1 = tr[u << 1 | 1].rmax1 = tr[u << 1 | 1].max1 = 0;
tr[u << 1].tagzero = tr[u << 1 | 1].tagzero = 1;
tr[u << 1].tagone = tr[u << 1 | 1].tagone = 0;
tr[u << 1].rev = tr[u << 1 | 1].rev = 0;
tr[u].tagzero = 0;
}
if(tr[u].tagone){
tr[u << 1].one = tr[u << 1].lmax1 = tr[u << 1].rmax1 = tr[u << 1].max1 = (tr[u << 1].r - tr[u << 1].l + 1);
tr[u << 1].zero = tr[u << 1].lmax0 = tr[u << 1].rmax0 = tr[u << 1].max0 = 0;
tr[u << 1 | 1].one = tr[u << 1 | 1].lmax1 = tr[u << 1 | 1].rmax1 = tr[u << 1 | 1].max1 = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
tr[u << 1 | 1].zero = tr[u << 1 | 1].lmax0 = tr[u << 1 | 1].rmax0 = tr[u << 1 | 1].max0 = 0;
tr[u << 1].tagone = tr[u << 1 | 1].tagone = 1;
tr[u << 1].tagzero = tr[u << 1 | 1].tagzero = 0;
tr[u << 1].rev = tr[u << 1 | 1].rev = 0;
tr[u].tagone = 0;
}
if(tr[u].rev){
swap(tr[u << 1].one , tr[u << 1].zero);
swap(tr[u << 1].lmax1 , tr[u << 1].lmax0);
swap(tr[u << 1].rmax1 , tr[u << 1].rmax0);
swap(tr[u << 1].max0 , tr[u << 1].max1);
swap(tr[u << 1 | 1].one , tr[u << 1 | 1].zero);
swap(tr[u << 1 | 1].lmax1 , tr[u << 1 | 1].lmax0);
swap(tr[u << 1 | 1].rmax1 , tr[u << 1 | 1].rmax0);
swap(tr[u << 1 | 1].max0 , tr[u << 1 | 1].max1);
tr[u << 1].rev ^= 1; tr[u << 1 | 1].rev ^= 1;
tr[u << 1].tagone = tr[u << 1].tagzero = 0;
tr[u << 1 | 1].tagone = tr[u << 1 | 1].tagzero = 0;
tr[u].rev = 0;
}
}
void build(int u , int l , int r){
if(l == r){
if(a[l]) tr[u] = {l , r , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1};
if(!a[l]) tr[u] = {l , r , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 0};
return ;
}
tr[u] = {l , r};
tr[u].tagone = tr[u].tagzero = tr[u].rev = 0;
int mid = l + r >> 1;
build(u << 1 , l , mid); build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
void assign0(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].one = 0;
tr[u].zero = tr[u].r - tr[u].l + 1;
tr[u].tagzero = 1;
tr[u].tagone = tr[u].rev = 0;
tr[u].lmax0 = tr[u].rmax0 = tr[u].r - tr[u].l + 1;
tr[u].lmax1 = tr[u].rmax1 = 0;
tr[u].max0 = tr[u].r - tr[u].l + 1;
tr[u].max1 = 0;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) assign0(u << 1 , l , r);
else if(l > mid) assign0(u << 1 | 1 , l , r);
else assign0(u << 1 , l , mid) , assign0(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
void assign1(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].zero = 0;
tr[u].one = tr[u].r - tr[u].l + 1;
tr[u].tagone = 1;
tr[u].tagzero = tr[u].rev = 0;
tr[u].lmax1 = tr[u].rmax1 = tr[u].r - tr[u].l + 1;
tr[u].lmax0 = tr[u].rmax0 = 0;
tr[u].max1 = tr[u].r - tr[u].l + 1;
tr[u].max0 = 0;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) assign1(u << 1 , l , r);
else if(l > mid) assign1(u << 1 | 1 , l , r);
else assign1(u << 1 , l , mid) , assign1(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
void reverse(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r){
swap(tr[u].one , tr[u].zero);
swap(tr[u].lmax1 , tr[u].lmax0);
swap(tr[u].rmax1 , tr[u].rmax0);
swap(tr[u].max0 , tr[u].max1);
tr[u].rev ^= 1;
tr[u].tagone = tr[u].tagzero = 0;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) reverse(u << 1 , l , r);
else if(l > mid) reverse(u << 1 | 1 , l , r);
else reverse(u << 1 , l , mid) , reverse(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
int ask(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].one;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return ask(u << 1 , l , r);
else if(l > mid) return ask(u << 1 | 1 , l , r);
else return ask(u << 1 , l , mid) + ask(u << 1 | 1 , mid + 1 , r);
}
node query(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1 , l , r);
else if(l > mid) return query(u << 1 | 1 , l , r);
else{
node L = query(u << 1 , l , mid);
node R = query(u << 1 | 1 , mid + 1 , r);
node ans;
update(ans , L , R);
return ans;
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
build(1 , 1 , n);
while(m--){
int opt , l , r;
scanf("%d%d%d" , &opt , &l , &r); ++l; ++r;
if(opt == 0) assign0(1 , l , r);
if(opt == 1) assign1(1 , l , r);
if(opt == 2) reverse(1 , l , r);
if(opt == 3) printf("%d\n" , ask(1 , l , r));
if(opt == 4) printf("%d\n" , query(1 , l , r).max1);
}
return 0;
}