02Ljh @ 2023-03-01 22:15:59
hack/样例全过
// Problem: P2572 [SCOI2010] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2572
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
//#define int long long
#define ull unsigned long long
#define ll long long
#define MAXN 100019
#define WA cout<<"CCF\n";
#define eps 1e-5
#define ls i*2
#define rs i*2+1
#define none -1145141919
#define pii pair<int,int>
#define Y cout<<"Yes\n"
#define N cout<<"No\n"
#define H cout<<"\n"
struct lxy
{
int n1,n0;
int tagr;//reverse
int tag0,tag1;
int l,r;
int lm1,rm1,all1;//all1 for 1
int lm0,rm0,all0;//all1 for 0
} tree[MAXN*4];
int n,m;
int input[MAXN];
void pr()
{
cout<<"pr start=\npos_=";
for(int i=1;i<=25;i++) cout<<setw(2)<<i<<" ";
cout<<"\nin1_=";
for(int i=1;i<=25;i++) cout<<setw(2)<<tree[i].n1<<" ";
cout<<"\ntag1=";
for(int i=1;i<=25;i++) cout<<setw(2)<<tree[i].tag1<<" ";
cout<<"\ntagr=";
for(int i=1;i<=25;i++) cout<<setw(2)<<tree[i].tagr<<" ";
cout<<"\n------------------\n";
return ;
}
int dis(int i)
{
return tree[i].r-tree[i].l+1;
}
void pushup(int i)
{
tree[i].n1=tree[ls].n1+tree[rs].n1;
tree[i].n0=tree[ls].n0+tree[rs].n0;
tree[i].lm1=max(tree[ls].lm1,(dis(ls)==tree[ls].n1)*(tree[rs].lm1+tree[ls].n1));
tree[i].rm1=max(tree[rs].rm1,(dis(rs)==tree[rs].n1)*(tree[ls].rm1+tree[rs].n1));
tree[i].all1=max({tree[ls].all1,tree[ls].rm1+tree[rs].lm1,tree[rs].all1});
tree[i].lm0=max(tree[ls].lm0,(dis(ls)==tree[ls].n1)*(tree[rs].lm0+tree[ls].n1));
tree[i].rm0=max(tree[rs].rm0,(dis(rs)==tree[rs].n1)*(tree[ls].rm0+tree[rs].n1));
tree[i].all0=max({tree[ls].all0,tree[ls].rm0+tree[rs].lm0,tree[rs].all0});
return ;
}
void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].tag1=tree[i].tag0=tree[i].tagr=tree[i].lm1=tree[i].rm1=tree[i].all1=0;
tree[i].lm0=tree[i].rm0=tree[i].all0=0;
tree[i].n1=tree[i].n0=0;
if(l==r)
{
if(input[l]==1)
{
tree[i].n1=1;
tree[i].n0=0;
tree[i].lm1=tree[i].rm1=tree[i].all1=1;
tree[i].lm0=tree[i].rm0=tree[i].all0=0;
}
else
{
tree[i].n0=1;
tree[i].n1=0;
tree[i].lm1=tree[i].rm1=tree[i].all1=0;
tree[i].lm0=tree[i].rm0=tree[i].all0=1;
}
return ;
}
int mid=(l+r)/2;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
return ;
}
void pushdown(int i)
{
if(tree[i].tag1)
{
tree[i].tag1=0;
tree[ls].tag1=tree[rs].tag1=1;
tree[ls].n1=dis(ls);
tree[ls].n0=0;
tree[ls].lm1=tree[ls].rm1=tree[ls].all1=dis(ls);
tree[ls].lm0=tree[ls].rm0=tree[ls].all0=0;
tree[ls].tag0=0;
tree[ls].tagr=0;
tree[rs].n1=dis(rs);
tree[rs].n0=0;
tree[rs].lm1=tree[rs].rm1=tree[rs].all1=dis(rs);
tree[rs].lm0=tree[rs].rm0=tree[rs].all0=0;
tree[rs].tag0=0;
tree[rs].tagr=0;
}
if(tree[i].tag0)
{
tree[i].tag0=0;
tree[ls].tag0=tree[rs].tag0=1;
tree[ls].n0=dis(ls);
tree[ls].n1=0;
tree[ls].lm1=tree[ls].rm1=tree[ls].all1=0;
tree[ls].lm0=tree[ls].rm0=tree[ls].all0=dis(ls);
tree[ls].tag1=0;
tree[ls].tagr=0;
tree[rs].n0=dis(rs);
tree[rs].n1=0;
tree[rs].lm1=tree[rs].rm1=tree[rs].all1=0;
tree[rs].lm0=tree[rs].rm0=tree[rs].all0=dis(rs);
tree[rs].tag1=0;
tree[rs].tagr=0;
}
tree[i].tagr%=2;
if(tree[i].tagr)
{
tree[i].tagr=0;
tree[ls].tagr++;
tree[rs].tagr++;
tree[ls].tagr%=2;
tree[rs].tagr%=2;
if(tree[ls].tagr)
{
swap(tree[ls].n1,tree[ls].n0);
swap(tree[ls].lm1,tree[ls].lm0);
swap(tree[ls].rm1,tree[ls].rm0);
swap(tree[ls].all1,tree[ls].all0);
tree[ls].tag1=0;
tree[ls].tag0=0;
}
if(tree[rs].tagr)
{
swap(tree[rs].n1,tree[rs].n0);
swap(tree[rs].lm1,tree[rs].lm0);
swap(tree[rs].rm1,tree[rs].rm0);
swap(tree[rs].all1,tree[rs].all0);
tree[rs].tag1=0;
tree[rs].tag0=0;
}
}
return ;
}
int query_1num(int l,int r,int i)
{
pushdown(i);
if(tree[i].l>=l&&tree[i].r<=r) return tree[i].n1;
if(tree[i].r<l||tree[i].l>r) return 0;
int ans=0;
if(tree[ls].r>=l) ans+=query_1num(l,r,ls);
if(tree[rs].l<=r) ans+=query_1num(l,r,rs);
pushup(i);
return ans;
}
void get0(int l,int r,int i)
{
pushdown(i);
if(tree[i].l>=l&&tree[i].r<=r)
{
tree[i].n1=0;
tree[i].n0=dis(i);
tree[i].lm1=tree[i].rm1=tree[i].all1=0;
tree[i].lm0=tree[i].rm0=tree[i].all0=dis(i);
tree[i].tag1=0;
tree[i].tag0=1;
tree[i].tagr=0;
return ;
}
//pushdown(i);
if(tree[i].r<l||tree[i].l>r) return ;
if(tree[ls].r>=l) get0(l,r,ls);
if(tree[rs].l<=r) get0(l,r,rs);
pushup(i);
return ;
}
void get1(int l,int r,int i)
{
pushdown(i);
if(tree[i].l>=l&&tree[i].r<=r)
{
tree[i].n1=dis(i);
tree[i].n0=0;
tree[i].lm1=tree[i].rm1=tree[i].all1=dis(i);
tree[i].lm0=tree[i].rm0=tree[i].all0=0;
tree[i].tag1=1;
tree[i].tag0=0;
tree[i].tagr=0;
return ;
}
//pushdown(i);
if(tree[i].r<l||tree[i].l>r) return ;
if(tree[ls].r>=l) get1(l,r,ls);
if(tree[rs].l<=r) get1(l,r,rs);
pushup(i);
return ;
}
void rever(int l,int r,int i)
{
pushdown(i);
if(tree[i].l>=l&&tree[i].r<=r)
{
tree[i].tagr++;
tree[i].tagr%=2;
if(tree[i].tagr==0) return ;
swap(tree[i].n1,tree[i].n0);
swap(tree[i].lm1,tree[i].lm0);
swap(tree[i].rm1,tree[i].rm0);
swap(tree[i].all1,tree[i].all0);
tree[i].tag1=0;
tree[i].tag0=0;
return ;
}
//pushdown(i);
if(tree[i].r<l||tree[i].l>r) return ;
if(tree[ls].r>=l) rever(l,r,ls);
if(tree[rs].l<=r) rever(l,r,rs);
pushup(i);
return ;
}
lxy getmax(int l,int r,int i)
{
pushdown(i);
if(tree[i].l>=l&&tree[i].r<=r) return tree[i];
if(tree[ls].r>=r) return getmax(l,r,ls);
if(tree[rs].l<=l) return getmax(l,r,rs);
else
{
lxy xx1=getmax(l,r,ls);
lxy yy1=getmax(l,r,rs);
lxy ne;
ne.lm1=max(xx1.lm1,(dis(ls)==xx1.n1)*(yy1.lm1+xx1.n1));
ne.rm1=max(yy1.rm1,(dis(rs)==yy1.n1)*(xx1.rm1+yy1.n1));
ne.all1=max({xx1.all1,xx1.rm1+yy1.lm1,yy1.all1});
return ne;
}
pushup(i);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>input[i];
build(1,1,n);
//cout<<tree[1].all1<<"\n";
while(m--)
{
int op,l,r;
cin>>op>>l>>r;
l++;
r++;
//pr();
switch(op)
{
case 0:
{
get0(l,r,1);
break;
}
case 1:
{
get1(l,r,1);
break;
}
case 2:
{
rever(l,r,1);
break;
}
case 3:
{
cout<<query_1num(l,r,1)<<"\n";
break;
}
case 4:
{
//WA;
cout<<getmax(l,r,1).all1<<"\n";
break;
}
}
//pr();
}
return 0;
}