MCRS_lizi @ 2022-08-02 19:26:31
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a[N],id[N],tot,blk;
struct sb
{
int val,lazy1,lazy2,l,r;
int len1,len2,len3;
int len4,len5,len6;
}b[1001];
void pushdown(int p)
{
for(int i=b[p].l;i<=b[p].r;i++)
{
if(b[p].lazy2)
{
a[i]=!a[i];
}
else if(b[p].lazy1!=-1)
{
a[i]=b[p].lazy1;
}
}
b[p].lazy1=-1;
b[p].lazy2=0;
}
void clear(int p)
{
int sum[2]={0,0};
for(int i=b[p].l;i<=b[p].r;i++)
{
sum[a[i]]++;
sum[!a[i]]=0;
b[p].len2=max(sum[1],b[p].len2);
b[p].len5=max(sum[0],b[p].len5);
}
int num=1;
for(int i=b[p].l+1;i<=b[p].r;i++)
{
if(a[i]!=a[i-1])
{
if(a[i-1])
{
b[p].len1=num;
b[p].len4=0;
}
else
{
b[p].len4=num;
b[p].len1=0;
}
break;
}
num++;
}
if(num==1+b[p].r-b[p].l)
{
if(a[b[p].l])
{
b[p].len1=num;
b[p].len4=0;
}
else
{
b[p].len4=num;
b[p].len1=0;
}
}
num=1;
for(int i=b[p].r-1;i>=b[p].l;i--)
{
if(a[i]!=a[i+1])
{
if(a[i+1])
{
b[p].len3=num;
b[p].len6=0;
}
else
{
b[p].len3=num;
b[p].len6=0;
}
break;
}
num++;
}
if(num==1+b[p].r-b[p].l)
{
if(a[b[p].l])
{
b[p].len3=num;
b[p].len6=0;
}
else
{
b[p].len6=num;
b[p].len3=0;
}
}
}
void update(int l,int r,int q)
{
if(id[l]==id[r])
{
pushdown(id[l]);
for(int i=l;i<=r;i++)
{
b[id[l]].val+=q-a[i];
a[i]=q;
}
clear(id[l]);
}
else
{
pushdown(id[l]);
pushdown(id[r]);
for(int i=l;i<=b[id[l]].r;i++)
{
b[id[l]].val+=q-a[i];
a[i]=q;
}
for(int i=b[id[r]].l;i<=r;i++)
{
b[id[r]].val+=q-a[i];
a[i]=q;
}
for(int i=id[l]+1;i<id[r];i++)
{
b[i].val=(b[i].r-b[i].l+1)*q;
b[i].lazy1=q;
b[i].lazy2=0;
if(q)
{
b[i].len1=b[i].len2=b[i].len3=b[i].r-b[i].l+1;
b[i].len4=b[i].len5=b[i].len6=0;
}
else
{
b[i].len1=b[i].len2=b[i].len3=0;
b[i].len4=b[i].len5=b[i].len6=b[i].r-b[i].l+1;
}
}
clear(id[l]);
clear(id[r]);
}
}
void change(int l,int r)
{
if(id[l]==id[r])
{
pushdown(id[l]);
for(int i=l;i<=r;i++)
{
if(a[i])
{
b[id[l]].val--;
}
else
{
b[id[l]].val++;
}
a[i]=!a[i];
}
clear(id[l]);
}
else
{
pushdown(id[l]);
pushdown(id[r]);
for(int i=l;i<=b[id[l]].r;i++)
{
if(a[i])
{
b[id[l]].val--;
}
else
{
b[id[l]].val++;
}
a[i]=!a[i];
}
for(int i=b[id[r]].l;i<=r;i++)
{
if(a[i])
{
b[id[r]].val--;
}
else
{
b[id[r]].val++;
}
a[i]=!a[i];
}
clear(id[l]);
clear(id[r]);
for(int i=id[l]+1;i<id[r];i++)
{
if(b[i].lazy1!=-1)
{
b[i].lazy1=!b[i].lazy1;
}
else
{
b[i].lazy2=!b[i].lazy2;
}
b[i].val=(b[i].r-b[i].l+1)-b[i].val;
swap(b[i].len1,b[i].len4);
swap(b[i].len2,b[i].len5);
swap(b[i].len3,b[i].len6);
}
}
}
int query1(int l,int r)
{
int res=0;
if(id[l]==id[r])
{
pushdown(id[l]);
for(int i=l;i<=r;i++)
{
res+=a[i];
}
}
else
{
pushdown(id[l]);
pushdown(id[r]);
for(int i=l;i<=b[id[l]].r;i++)
{
res+=a[i];;
}
for(int i=b[id[r]].l;i<=r;i++)
{
res+=a[i];
}
for(int i=id[l]+1;i<id[r];i++)
{
res+=b[i].val;
}
}
return res;
}
int query2(int l,int r)
{
int res=0,cnt=0;
if(id[l]==id[r])
{
pushdown(id[l]);
for(int i=l;i<=r;i++)
{
if(a[i])
{
cnt++;
}
else
{
cnt=0;
}
res=max(cnt,res);
}
}
else
{
pushdown(id[l]);
pushdown(id[r]);
for(int i=l;i<=b[id[l]].r;i++)
{
if(a[i])
{
cnt++;
}
else
{
cnt=0;
}
res=max(cnt,res);
}
for(int i=id[l]+1;i<id[r];i++)
{
cnt+=b[i].len1;
res=max(res,max(b[i].len2,cnt));
if(b[i].len1!=b[i].len3)
{
cnt=b[i].len3;
}
}
for(int i=b[id[r]].l;i<=r;i++)
{
if(a[i])
{
cnt++;
}
else
{
cnt=0;
}
res=max(cnt,res);
}
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m;
blk=sqrt(n);
int sum[2]={0,0},flag[2]={0,0};
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(flag[a[i]]==0&&flag[!a[i]]==1)
{
flag[!a[i]]==0;
if(a[i])
{
b[tot].len1=0;
b[tot].len4=sum[0];
}
else
{
b[tot].len4=0;
b[tot].len1=sum[1];
}
}
sum[a[i]]++;
sum[!a[i]]=0;
if(i%blk==0)
{
b[tot].r=i;
b[tot].len3=sum[1];
b[tot].len6=sum[0];
}
else if(i%blk==1)
{
b[++tot].l=i;
flag[a[i]]=1;
flag[!a[i]]=0;
}
b[tot].len2=max(b[tot].len2,sum[1]);
b[tot].len5=max(b[tot].len5,sum[0]);
id[i]=tot;
b[tot].val+=a[i];
b[tot].lazy1=-1;
}
while(m--)
{
int q,l,r;
cin>>q>>l>>r;
l++,r++;
if(q<=1)
{
update(l,r,q);
}
else if(q==2)
{
change(l,r);
}
else if(q==3)
{
printf("%d\n",query1(l,r));
}
else
{
printf("%d\n",query2(l,r));
}
// for(int i=1;i<=tot;i++)
// {
// pushdown(i);
// }
// for(int i=1;i<=n;i++)
// {
// cout<<a[i]<<" ";
// }
// cout<<endl;
}
return 0;
}
RT,本蒟蒻悬赏一个关注qwq
by MCRS_lizi @ 2022-08-02 19:27:21
懒得写线段树,写的分块QAQ
by MCRS_lizi @ 2022-08-02 19:36:05
至少现在对拍出错误数据了
by MCRS_lizi @ 2022-08-02 19:45:39
发现了一个错误,但还是只有10pts qaq