Mathew_Miao @ 2023-02-17 21:26:25
代码很丑
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=400;
int n,m;
int len,tot;
bool a[MAXN];
int idx[MAXN];
struct block{
bool all0,all1; //全0 全1
int l0,r0; //最长前缀0 最长后缀0
int l1,r1; //最长前缀1 最长后缀1
int cnt0,cnt1; //0的数量 1的数量
int l,r,len; //块左端 块右端 块长
bool rev; //反转
void init(){
if(all0){
for(int i=l;i<=r;i++)
{
a[i]=0;
}
}
if(all1){
for(int i=l;i<=r;i++)
{
a[i]=1;
}
}
if(rev){
for(int i=l;i<=r;i++)
{
a[i]=!a[i];
}
}
all0=false;
all1=false;
rev=false;
}
void build(){
for(int i=l;i<=r;i++)
{
if(a[i]){
l0=i-1;
break;
}
}
for(int i=l;i<=r;i++)
{
if(!a[i]){
l1=i-1;
break;
}
}
for(int i=r;i>=l;i--)
{
if(a[i]){
r0=n-i;
break;
}
}
for(int i=r;i>=l;i--)
{
if(!a[i]){
r1=n-i;
break;
}
}
cnt0=0;
cnt1=0;
for(int i=l;i<=r;i++)
{
if(a[i]){
cnt1++;
}
else{
cnt0++;
}
}
}
}b[MAXN];
void All_0(int l,int r){
if(idx[l]==idx[r]){
b[idx[l]].init();
for(int i=l;i<=r;i++)
{
a[i]=0;
}
b[idx[l]].build();
return ;
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
b[i].all0=true;
b[i].all1=false;
b[i].l0=b[i].len;
b[i].r0=b[i].len;
b[i].l1=0;
b[i].r1=0;
b[i].cnt0=b[i].len;
b[i].cnt1=0;
}
b[idx[l]].init();
b[idx[r]].init();
for(int i=l;idx[i]==idx[l];i++)
{
a[i]=0;
}
for(int i=r;idx[i]==idx[r];i--)
{
a[i]=0;
}
b[idx[l]].build();
b[idx[r]].build();
}
void All_1(int l,int r){
if(idx[l]==idx[r]){
b[idx[l]].init();
for(int i=l;i<=r;i++)
{
a[i]=1;
}
b[idx[l]].build();
return ;
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
b[i].all0=false;
b[i].all1=true;
b[i].l0=0;
b[i].r0=0;
b[i].l1=b[i].len;
b[i].r1=b[i].len;
b[i].cnt0=0;
b[i].cnt1=b[i].len;
}
b[idx[l]].init();
b[idx[r]].init();
for(int i=l;idx[i]==idx[l];i++)
{
a[i]=1;
}
for(int i=r;idx[i]==idx[r];i--)
{
a[i]=1;
}
b[idx[l]].build();
b[idx[r]].build();
}
void Rev(int l,int r){
if(idx[l]==idx[r]){
b[idx[l]].init();
for(int i=l;i<=r;i++)
{
a[i]=!a[i];
}
b[idx[l]].build();
return ;
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
b[i].rev=true;
swap(b[i].l0,b[i].r0);
swap(b[i].l1,b[i].r1);
swap(b[i].cnt1,b[i].cnt1);
}
b[idx[l]].init();
b[idx[r]].init();
for(int i=l;idx[i]==idx[l];i++)
{
a[i]=!a[i];
}
for(int i=r;idx[i]==idx[r];i--)
{
a[i]=!a[i];
}
b[idx[l]].build();
b[idx[r]].build();
}
int Cnt1(int l,int r){
if(idx[l]==idx[r]){
int res=0;
b[idx[l]].init();
b[idx[l]].build();
for(int i=l;i<=r;i++)
{
res+=a[i];
}
return res;
}
int res=0;
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
res+=b[i].cnt1;
}
b[idx[l]].init();
b[idx[r]].init();
b[idx[l]].build();
b[idx[r]].build();
for(int i=l;idx[i]==idx[l];i++)
{
res+=a[i];
}
for(int i=r;idx[i]==idx[r];i--)
{
res+=a[i];
}
return res;
}
int LX1(int l,int r){
if(idx[l]==idx[r]){
int res=0,lst=l;
b[idx[l]].init();
b[idx[l]].build();
for(int i=l;i<=r;i++)
{
if(a[i]==0){
res=max(res,i-lst);
lst=i+1;
}
}
res=max(res,r-lst+1);
return res;
}
int res=0;
int lst=l;
b[idx[l]].init();
b[idx[l]].build();
for(int i=l;idx[i]==idx[l];i++)
{
if(a[i]==0){
res=max(res,i-lst);
lst=i+1;
}
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
if(b[i].l1!=b[i].len){
res=max(res,b[i].l+b[i].l1-1-lst+1);
lst=b[i].r-b[i].r1+1;
}
}
b[idx[r]].init();
b[idx[r]].build();
for(int i=r;idx[i]==idx[r];i--)
{
if(a[i]==0){
res=max(res,i-lst);
lst=i+1;
}
}
res=max(res,r-lst+1);
return res;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
len=(int)sqrt(n);
tot=(n+len-1)/len;
for(int i=1;i<=tot;i++)
{
b[i].l=(i-1)*len+1;
b[i].r=min(i*len,n);
b[i].len=b[i].r-b[i].l+1;
b[i].build();
for(int j=b[i].l;j<=b[i].r;j++)
{
idx[j]=i;
}
}
while(m--)
{
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
switch(opt)
{
case 0:
All_0(l,r);
break;
case 1:
All_1(l,r);
break;
case 2:
Rev(l,r);
break;
case 3:
printf("%d\n",Cnt1(l,r));
break;
case 4:
printf("%d\n",LX1(l,r));
break;
}
}
return 0;
}by Mathew_Miao @ 2023-02-18 07:26:15
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=400;
int n,m;
int len,tot;
bool a[MAXN];
int idx[MAXN];
struct block{
bool all0,all1; //全0 全1
int l0,r0; //最长前缀0 最长后缀0
int l1,r1; //最长前缀1 最长后缀1
int len0,len1; //块中最长0 块中最长1
int cnt0,cnt1; //0的数量 1的数量
int l,r,len; //块左端 块右端 块长
bool rev; //反转
void init(){
if(all0){
for(int i=l;i<=r;i++)
{
a[i]=0;
}
}
if(all1){
for(int i=l;i<=r;i++)
{
a[i]=1;
}
}
if(rev){
for(int i=l;i<=r;i++)
{
a[i]=!a[i];
}
}
all0=false;
all1=false;
rev=false;
}
void build(){
l0=len;
for(int i=l;i<=r;i++)
{
if(a[i]){
l0=i-l;
break;
}
}
l1=len;
for(int i=l;i<=r;i++)
{
if(!a[i]){
l1=i-l;
break;
}
}
r0=len;
for(int i=r;i>=l;i--)
{
if(a[i]){
r0=r-i;
break;
}
}
r1=len;
for(int i=r;i>=l;i--)
{
if(!a[i]){
r1=r-i;
break;
}
}
cnt0=0;
cnt1=0;
for(int i=l;i<=r;i++)
{
if(a[i]){
cnt1++;
}
else{
cnt0++;
}
}
int lst;
lst=l;
for(int i=l;i<=r;i++)
{
if(a[i]==1){
len0=max(len0,i-lst);
lst=i+1;
}
}
len0=max(len0,r-lst+1);
lst=l;
for(int i=l;i<=r;i++)
{
if(a[i]==0){
len1=max(len1,i-lst);
lst=i+1;
}
}
len1=max(len1,r-lst+1);
}
}b[MAXN];
void All_0(int l,int r){
if(idx[l]==idx[r]){
b[idx[l]].init();
for(int i=l;i<=r;i++)
{
a[i]=0;
}
b[idx[l]].build();
return ;
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
b[i].all0=true;
b[i].all1=false;
b[i].l0=b[i].len;
b[i].r0=b[i].len;
b[i].l1=0;
b[i].r1=0;
b[i].cnt0=b[i].len;
b[i].cnt1=0;
b[i].len0=b[i].len;
b[i].len1=0;
}
b[idx[l]].init();
b[idx[r]].init();
for(int i=l;idx[i]==idx[l];i++)
{
a[i]=0;
}
for(int i=r;idx[i]==idx[r];i--)
{
a[i]=0;
}
b[idx[l]].build();
b[idx[r]].build();
}
void All_1(int l,int r){
if(idx[l]==idx[r]){
b[idx[l]].init();
for(int i=l;i<=r;i++)
{
a[i]=1;
}
b[idx[l]].build();
return ;
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
b[i].all0=false;
b[i].all1=true;
b[i].l0=0;
b[i].r0=0;
b[i].l1=b[i].len;
b[i].r1=b[i].len;
b[i].cnt0=0;
b[i].cnt1=b[i].len;
b[i].len0=0;
b[i].len1=b[i].len;
}
b[idx[l]].init();
b[idx[r]].init();
for(int i=l;idx[i]==idx[l];i++)
{
a[i]=1;
}
for(int i=r;idx[i]==idx[r];i--)
{
a[i]=1;
}
b[idx[l]].build();
b[idx[r]].build();
}
void Rev(int l,int r){
if(idx[l]==idx[r]){
b[idx[l]].init();
for(int i=l;i<=r;i++)
{
a[i]=!a[i];
}
b[idx[l]].build();
return ;
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
b[i].rev=true;
swap(b[i].l0,b[i].l1);
swap(b[i].r0,b[i].r1);
swap(b[i].cnt0,b[i].cnt1);
swap(b[i].len0,b[i].len1);
}
b[idx[l]].init();
b[idx[r]].init();
for(int i=l;idx[i]==idx[l];i++)
{
a[i]=!a[i];
}
for(int i=r;idx[i]==idx[r];i--)
{
a[i]=!a[i];
}
b[idx[l]].build();
b[idx[r]].build();
}
int Cnt1(int l,int r){
if(idx[l]==idx[r]){
int res=0;
b[idx[l]].init();
b[idx[l]].build();
for(int i=l;i<=r;i++)
{
res+=a[i];
}
return res;
}
int res=0;
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
res+=b[i].cnt1;
}
b[idx[l]].init();
b[idx[r]].init();
b[idx[l]].build();
b[idx[r]].build();
for(int i=l;idx[i]==idx[l];i++)
{
res+=a[i];
}
for(int i=r;idx[i]==idx[r];i--)
{
res+=a[i];
}
return res;
}
int LX1(int l,int r){
if(idx[l]==idx[r]){
int res=0,lst=l;
b[idx[l]].init();
b[idx[l]].build();
for(int i=l;i<=r;i++)
{
if(a[i]==0){
res=max(res,i-lst);
lst=i+1;
}
}
res=max(res,r-lst+1);
return res;
}
int res=0;
int lst=l;
b[idx[l]].init();
b[idx[l]].build();
for(int i=l;idx[i]==idx[l];i++)
{
if(a[i]==0){
res=max(res,i-lst);
lst=i+1;
}
}
for(int i=idx[l]+1;i<=idx[r]-1;i++)
{
res=max(res,b[i].len1);
if(b[i].l1!=b[i].len){
res=max(res,b[i].l+b[i].l1-1-lst+1);
lst=b[i].r-b[i].r1+1;
}
}
b[idx[r]].init();
b[idx[r]].build();
for(int i=r;idx[i]==idx[r];i--)
{
if(a[i]==0){
res=max(res,i-lst);
lst=i+1;
}
}
res=max(res,r-lst+1);
return res;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
len=(int)sqrt(n);
tot=(n+len-1)/len;
for(int i=1;i<=tot;i++)
{
b[i].l=(i-1)*len+1;
b[i].r=min(i*len,n);
b[i].len=b[i].r-b[i].l+1;
b[i].build();
for(int j=b[i].l;j<=b[i].r;j++)
{
idx[j]=i;
}
}
while(m--)
{
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
switch(opt)
{
case 0:
All_0(l,r);
break;
case 1:
All_1(l,r);
break;
case 2:
Rev(l,r);
break;
case 3:
printf("%d\n",Cnt1(l,r));
break;
case 4:
printf("%d\n",LX1(l,r));
break;
}
}
return 0;
}稍微改了一些智障错误