如果你想赤石||蒟蒻Qwq求调||玄关!!!

写的构式分块

当块长为 n 时,能过前三个点,其他会T显然

当块长为 sqrt(n) 时,只能过hack,其他点全Wa

合理怀疑是处理整块寄了,求调

代码只是看着长

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514];
struct Node
{
    int l,r;
    int lay;
    int cnt;
    int sum;
    int ls1,rs1,ans1;
    int ls2,rs2,ans2;
} b[1145];
int op,l,r;
int len;

inline void LS1(int x)
{
    int res=0;
    for(int i=b[x].l;i<=b[x].r;i++)
    {
        if(a[i])
          res++;
        else
          break;  
    }
    b[x].ls1=res;
}

inline void RS1(int x)
{
    int res=0;
    for(int i=b[x].r;i>=b[x].l;i--)
    {
        if(a[i])
          res++;
        else
          break;  
    }
    b[x].rs1=res;
}

inline void ANS1(int x)
{
    int res=0,maxx=0;
    for(int i=b[x].l;i<=b[x].r;i++)
    {
        if(a[i])
          res++;
        else
          res=0;
        maxx=max(maxx,res);   
    }
    b[x].ans1=maxx;
}

inline void LS2(int x)
{
    int res=0;
    for(int i=b[x].l;i<=b[x].r;i++)
    {
        if(!a[i])
          res++;
        else
          break;  
    }
    b[x].ls2=res;
}

inline void RS2(int x)
{
    int res=0;
    for(int i=b[x].r;i>=b[x].l;i--)
    {
        if(!a[i])
          res++;
        else
          break;  
    }
    b[x].rs2=res;
}

inline void ANS2(int x)
{
    int res=0,maxx=0;
    for(int i=b[x].l;i<=b[x].r;i++)
    {
        if(!a[i])
          res++;
        else
          res=0;
        maxx=max(maxx,res);   
    }
    b[x].ans2=maxx;
}

inline void SUM(int x)
{
    int res=0;
    for(int i=b[x].l;i<=b[x].r;i++)
      res+=a[i];
    b[x].sum=res;  
}

inline void init(int x)
{
    LS1(x);
    RS1(x);
    ANS1(x);
    LS2(x);
    RS2(x);
    ANS2(x);
    SUM(x);
}

inline void change(int l,int r,int k)
{
    int x=(l-1)/len+1;
    int y=(r-1)/len+1;
    if(x==y)
    {
        for(int i=l;i<=r;i++)
          a[i]=k;
        init(x);  
    }
    else
    {
        for(int i=l;i<=b[x].r;i++)
          a[i]=k;
        init(x);  
        for(int i=x+1;i<=y-1;i++)
        {
            b[i].lay=k+1;
            b[i].cnt=0; 
            b[i].sum=k*len;
            if(k)
            {
                b[i].ls1=len;b[i].ls2=0;
                b[i].rs1=len;b[i].rs2=0;
                b[i].ans1=len;b[i].ans2=0;
            } 
            else
            {
                b[i].ls1=0;b[i].ls2=len;
                b[i].rs1=0;b[i].rs2=len;
                b[i].ans1=0;b[i].ans2=len;
            }
        }
        for(int i=b[y].l;i<=r;i++)
          a[i]=k;  
        init(y);  
    }
}

inline void fan(int l,int r)
{
    int x=(l-1)/len+1;
    int y=(r-1)/len+1;
    int cnt;
    if(x==y)
    {
        for(int i=b[x].l;i<=b[x].r;i++)
        {
            if(b[x].lay==1)
              a[i]=0;
            else if(b[x].lay==2)
              a[i]=1;    
            if(l<=i&&i<=r)   
            a[i]=a[i]^1^b[x].cnt;
        }  
        b[x].lay=0;
        b[x].cnt=0;
        init(x);  
    }
    else
    {
        for(int i=b[x].l;i<=b[x].r;i++)
        {
            if(b[x].lay==1)
              a[i]=0;
            else if(b[x].lay==2)
              a[i]=1;  
            if(i>=l)     
            a[i]=a[i]^1^b[x].cnt;
        }
        b[x].lay=0;
        b[x].cnt=0;
        init(x);  
        for(int i=x+1;i<=y-1;i++)
        {
            b[i].sum=len-b[i].sum;
            b[i].cnt=1^b[i].cnt;
            swap(b[i].ls1,b[i].ls2);
            swap(b[i].rs1,b[i].rs2);
            swap(b[i].ans1,b[i].ans2);
        }     
        for(int i=b[y].l;i<=b[y].r;i++)
        {
            if(b[y].lay==1)
              a[i]=0;
            else if(b[y].lay==2)
              a[i]=1;   
            if(i<=r)      
            a[i]=a[i]^1^b[y].cnt;
        }
        b[y].lay=0;
        b[y].cnt=0;
        init(y);     
    }
}

inline void ask1(int l,int r)
{
    int x=(l-1)/len+1;
    int y=(r-1)/len+1;
    int ans=0;

    if(x==y)
    {
        for(int i=b[x].l;i<=b[x].r;i++)
        {
            if(b[x].lay==1)
              a[i]=0;
            if(b[x].lay==2)
              a[i]=1;
            a[i]=a[i]^b[x].cnt;
            if(l<=i&&i<=r)
            ans+=a[i];    
        }
        b[x].lay=0;
        b[x].cnt=0;
        init(x);
    }
    else
    {
        for(int i=b[x].l;i<=b[x].r;i++)
        {
            if(b[x].lay==1)
              a[i]=0;
            if(b[x].lay==2)
              a[i]=1;
            a[i]=a[i]^b[x].cnt;
            if(i>=l)
              ans+=a[i];      
        }
        b[x].lay=0;
        b[x].cnt=0;
        init(x);

        for(int i=x+1;i<=y-1;i++)
            ans+=b[i].ans1;

        for(int i=b[y].l;i<=b[y].r;i++)
        {
            if(b[y].lay==1)
              a[i]=0;
            if(b[y].lay==2)
              a[i]=1;
            a[i]=a[i]^b[y].cnt;
            if(i<=r)
            ans+=a[i];    
        }
        b[y].lay=0;
        b[y].cnt=0;
        init(y);
    }
    cout<<ans<<'\n';
}

inline void ask2(int l,int r)
{
    int x=(l-1)/len+1;
    int y=(r-1)/len+1;
    int ans=0,res=0,sum=0;

    if(x==y)
    {
        for(int i=l;i<=r;i++)
        {
            if(b[x].lay==1)
              a[i]=0;
            if(b[x].lay==2)
              a[i]=1;
            a[i]=a[i]^b[x].cnt;
            if(a[i])
              res++;
            else
              res=0;
            ans=max(ans,res);             
        }
    }
    else
    {
        for(int i=b[x].l;i<=b[x].r;i++)
        {
            if(b[x].lay==1)
              a[i]=0;
            if(b[x].lay==2)
              a[i]=1;
            if(i>=l)
            {
                a[i]=a[i]^b[x].cnt;
                if(a[i])
                  res++;
                else
                  res=0;
                ans=max(ans,res);   
            }   
        }
        b[x].lay=0;
        b[x].cnt=0;
        init(x);

        for(int i=b[x].r;i>=l;i--)
          if(a[i])
            sum++;
          else
              break;    

        for(int i=x+1;i<=y-1;i++)
        {
            ans=max(ans,sum+b[i].ls1);
            ans=max(ans,b[i].ans1);
            if(b[i].rs1==len)
              sum+=b[i].rs1;
            else
              sum=b[i].rs1;  
        }

        res=0;
        for(int i=b[y].l;i<=b[y].r;i++)
        {
            if(b[y].lay==1)
              a[i]=0;
            if(b[y].lay==2)
              a[i]=1;
            a[i]=a[i]^b[y].cnt;
            if(y<=r)
            {
                if(a[i])
                  res++;
                else
                  res=0;
                ans=max(ans,res);     
            }     
        }
        b[y].lay=0;
        b[y].cnt=0;
        init(y);
        for(int i=b[y].l;i<=r;i++)
          if(a[i])
            sum++;
          else
              break;
        ans=max(ans,sum);         
    }
    cout<<ans<<'\n';
}

int main()
{
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        op=(i-1)/len+1;
        if((i-1)%len==0)
        {
            b[op].l=i;
            b[op-1].r=i-1;
        }
    }
    b[op].r=n;
    for(int i=1;i<=op;i++)
    {
        init(i);
        //cout<<b[i].sum<<'\n';
    }

    for(int i=1;i<=m;i++)
    {
        cin>>op>>l>>r;
        l++,r++;
        if(op==0)
            change(l,r,0);
        else if(op==1)
          change(l,r,1);
        else if(op==2)
          fan(l,r);
        else if(op==3)
          ask1(l,r);
        else
          ask2(l,r);          
    } 

    return 0;
}