求条，样例都过不了

Fish_Love_Water @ 2024-12-20 19:48:11

#include<bits/stdc++.h>
#define ls(u) u<<1
#define rs(u) u<<1|1
using namespace std;
const int N=1e5+5;
int n,m,a[N];
struct Tree{
    int l,r;
    int len,sa,sb,la,lb,ra,rb,ma,mb;
    int lz1,lz2;
}t[N*4];
void pushup(Tree &T,Tree L,Tree R){
    T.la= L.lb? L.la:L.sa+R.la;
    T.ra= R.rb? R.ra:R.sa+L.ra;
    T.ma=max(max(L.ma,R.ma),R.la+L.ra);
    T.sa=L.sa+R.sa; 
    T.lb= L.la? L.lb:L.sb+R.lb;
    T.rb= R.ra? R.rb:R.sb+L.rb;
    T.mb=max(max(L.mb,R.mb),R.lb+L.rb);
    T.sb=L.sb+R.sb;
}
void change(Tree &T,int opt){
    if(opt==1){
        T.ma=T.la=T.ra=0;
        T.mb=T.lb=T.rb=T.len;
        T.lz1=1,T.lz2=0;
    }
    else if(opt==2){
        T.mb=T.lb=T.rb=0;
        T.ma=T.la=T.ra=T.len;
        T.lz1=2,T.lz2=0;
    }
    else if(opt==3){
        swap(T.sa,T.sb);
        swap(T.la,T.lb);
        swap(T.ra,T.rb);
        swap(T.ma,T.mb);
        T.lz2^=1;
    }
}
void pushdown(int u){
    Tree L=t[ls(u)];
    Tree R=t[rs(u)];
    if(t[u].lz1==1){
        change(L,1);
        change(R,1);
    }
    else if(t[u].lz1==2){
        change(L,2);
        change(R,2);
    }
    else if(t[u].lz2==1){
        change(L,3);
        change(R,3);
    }
    t[u].lz1=t[u].lz2=0;
}
void build(int u,int l,int r){
    t[u].l=l,t[u].r=r,t[u].len=r-l+1;
    if(l==r){
        if(a[l]) t[u].len=t[u].sa=t[u].la=t[u].ra=t[u].ma=1;
        else t[u].len=t[u].sb=t[u].lb=t[u].rb=t[u].mb=1;
        return;
    }
    int mid=(l+r)/2;
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    pushup(t[u],t[ls(u)],t[rs(u)]);
}
void update(int u,int l,int r,int k){
    if(t[u].l>=l&&t[u].r<=r){
        change(t[u],k);
        return;
    }
    int mid=(t[u].r+t[u].l)>>1;
    pushdown(u); 
    if(l<=mid) update(ls(u),l,r,k);
    if(r>mid) update(rs(u),l,r,k);
    pushup(t[u],t[ls(u)],t[rs(u)]);
}
Tree query(int u,int l,int r){
    if(t[u].l>=l&&t[u].r<=r) return t[u];
    int mid=(t[u].l+t[u].r)>>1;
    pushdown(u);
    if(l<=mid) return query(ls(u),l,r);
    if(r>mid) return query(rs(u),l,r);
    Tree T;
    pushup(T,query(ls(u),l,mid),query(rs(u),mid+1,r));
    return T;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int opt,l,r;
    for(int i=1;i<=m;i++){
        cin>>opt>>l>>r;
        l++,r++;
        if(opt<3) update(1,l,r,opt+1);
        else if(opt==3) cout<<query(1,l,r).sa<<endl;
        else cout<<query(1,l,r).ma<<endl;
    } 
    return 0;
}

by __Confringo__ @ 2024-12-20 19:51:01

免费食用

#include <bits/stdc++.h>
#define SBLeftSon p<<1
#define SBRightSon p<<1|1
#define pause system("pause")
using namespace std;

const int N = 1e5+5;
int n,m,a[N],op,l,r;
struct Tree{
    int l,r;
    int b,lb,rb,mb;
    int c,lc,rc,mc;
    int len,tag,rev;
}t[N*4];
void func(int p,int o){
    Tree &s = t[p];
    if (o == 0){
        s.b = s.lb = s.rb = s.mb = 0;
        s.c = s.lc = s.rc = s.mc = s.len;
        s.tag = 0;
        s.rev = 0;
    }else if (o == 1){
        s.b = s.lb = s.rb = s.mb = s.len;
        s.c = s.lc = s.rc = s.mc = 0;
        s.tag = 1;
        s.rev = 0;
    }else if (o == 2){
        swap(s.b,s.c);
        swap(s.lb,s.lc);
        swap(s.rb,s.rc);
        swap(s.mb,s.mc);
        s.rev ^= 1;
    }
}
void pushup(Tree &s,Tree l,Tree r){
    s.b = l.b + r.b;
    s.lb = l.c ? l.lb : l.b + r.lb;
    s.rb = r.c ? r.rb : r.b + l.rb;
    s.mb = max(max(l.mb,r.mb),l.rb + r.lb);
    s.c = l.c + r.c;
    s.lc = l.b ? l.lc : l.c + r.lc;
    s.rc = r.b ? r.rc : r.c + l.rc;
    s.mc = max(max(l.mc,r.mc),l.rc + r.lc);
}
void pushdown(int p){
    Tree &s = t[p];
    if (s.tag == 0) func(SBLeftSon,0),func(SBRightSon,0);
    if (s.tag == 1) func(SBLeftSon,1),func(SBRightSon,1);
    if (s.rev) func(SBLeftSon,2),func(SBRightSon,2);
    s.tag = -1;
    s.rev = 0;
}
void build(int p,int l,int r){
    int x = a[l];
    t[p] = {l,r,x,x,x,x,x^1,x^1,x^1,x^1,r-l+1,-1,0};
    if (l == r) return ;
    int m = (l + r) >> 1;
    build(SBLeftSon,l,m);
    build(SBRightSon,m+1,r);
    pushup(t[p],t[SBLeftSon],t[SBRightSon]);
    return ;
}
void change(int p,int x,int y,int k){
    if (t[p].l > y || t[p].r < x) return ;
    if (x <= t[p].l && t[p].r <= y){
        func(p,k);
        return ;
    }
    pushdown(p);
    change(SBLeftSon,x,y,k);
    change(SBRightSon,x,y,k);
    pushup(t[p],t[SBLeftSon],t[SBRightSon]);
}
Tree query(int p,int x,int y){
    if (t[p].l > y || t[p].r < x) return {};
    if (x <= t[p].l && t[p].r <= y) return t[p];
    pushdown(p);
    Tree ans;
    pushup(ans,query(SBLeftSon,x,y),query(SBRightSon,x,y));
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    build(1,1,n);
    while (m--){
        cin >> op >> l >> r;
        l++,r++;
        if (op <= 2) change(1,l,r,op);
        else{
            Tree Genshin = query(1,l,r);
            cout << (op == 3 ? Genshin.b : Genshin.mb) << endl;
        } 
    }
    pause;
    return 0;
}

by Fish_Love_Water @ 2024-12-20 20:07:09

改了一下，求条

#include<bits/stdc++.h>
#define ls(u) u<<1
#define rs(u) u<<1|1
using namespace std;
const int N=1e5+5;
int n,m,a[N];
struct Tree{
    int l,r;
    int len,sa,sb,la,lb,ra,rb,ma,mb;
    int lz1,lz2;
}t[N*4];
void pushup(Tree &T,Tree L,Tree R){
    T.la= L.lb? L.la:L.sa+R.la;
    T.ra= R.rb? R.ra:R.sa+L.ra;
    T.ma=max(max(L.ma,R.ma),R.la+L.ra);
    T.sa=L.sa+R.sa; 
    T.lb= L.la? L.lb:L.sb+R.lb;
    T.rb= R.ra? R.rb:R.sb+L.rb;
    T.mb=max(max(L.mb,R.mb),R.lb+L.rb);
    T.sb=L.sb+R.sb;
}
void change(Tree &T,int opt){
    if(opt==1){
        T.ma=T.la=T.ra=T.sa=0;
        T.mb=T.lb=T.rb=T.sb=T.len;
        T.lz1=1,T.lz2=0;
    }
    else if(opt==2){
        T.mb=T.lb=T.rb=T.sb=0;
        T.ma=T.la=T.ra=T.sa=T.len;
        T.lz1=2,T.lz2=0;
    }   
    else if(opt==3){
        swap(T.sa,T.sb);
        swap(T.la,T.lb);
        swap(T.ra,T.rb);
        swap(T.ma,T.mb);
        T.lz2^=1;
    }
}
void pushdown(int u){
    Tree L=t[ls(u)];
    Tree R=t[rs(u)];
    if(t[u].lz1==1){
        change(L,1);
        change(R,1);
    }
    if(t[u].lz1==2){
        change(L,2);
        change(R,2);
    }
    if(t[u].lz2==1){
        change(L,3);
        change(R,3);
    }
    t[u].lz1=t[u].lz2=0;
}
void build(int u,int l,int r){
    t[u].l=l,t[u].r=r,t[u].len=r-l+1;
    if(l==r){
        if(a[l]) t[u].len=t[u].sa=t[u].la=t[u].ra=t[u].ma=1;
        else t[u].len=t[u].sb=t[u].lb=t[u].rb=t[u].mb=1;
        return;
    }
    int mid=(l+r)/2;
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    pushup(t[u],t[ls(u)],t[rs(u)]);
}
void update(int u,int l,int r,int k){
    if(t[u].l>=l&&t[u].r<=r){
        change(t[u],k);
        return;
    }
    int mid=(t[u].r+t[u].l)>>1;
    pushdown(u); 
    if(l<=mid) update(ls(u),l,r,k);
    if(r>mid) update(rs(u),l,r,k);
    pushup(t[u],t[ls(u)],t[rs(u)]);
}
Tree query(int u,int l,int r){
    if(t[u].l>=l&&t[u].r<=r) return t[u];
    if(t[u].l>r||t[u].r<l) return {}; 
    int mid=(t[u].l+t[u].r)>>1;
    pushdown(u);
    if(l<=mid) return query(ls(u),l,r);
    if(r>mid) return query(rs(u),l,r);
    Tree T;
    pushup(T,query(ls(u),l,mid),query(rs(u),mid+1,r));
    return T;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int opt,l,r;
    for(int i=1;i<=m;i++){
        cin>>opt>>l>>r;
        l++,r++;
        if(opt<3) update(1,l,r,opt+1);
        else if(opt==3) cout<<query(1,l,r).sa<<endl;
        else cout<<query(1,l,r).ma<<endl;
    } 
    return 0;
}