z_yq @ 2024-06-27 08:47:47
AwA，改了18个小时了，含注释和调试语句，共161行，下面放没有调试的代码，共132行：
#include<bits/stdc++.h>
#define ll long long
#define lson(x) x<<1
#define rson(x) x<<1|1
using namespace std;
const ll N=1e5+9;
struct node
{
ll num1,num0;
ll left1,left0,right1,right0;
ll mid1,mid0;
ll lazy_f,lazy_q,lt,rt,len; //lazy_f 赋值标记(-1) lazy_q 取反标记(0)
}tr[N*4];
ll n,m,a[N];
inline node merge(node x,node y)
{
return node({
x.num1+y.num1,
x.num0+y.num0,
(x.num0?x.left1:x.num1+y.left1),
(x.num1?x.left0:x.num0+y.left0),
(y.num0?y.left1:y.num1+x.left1),
(y.num1?y.left0:y.num0+x.left0),
max(max(x.mid1,y.mid1),x.right1+y.left1),
max(max(x.mid0,y.mid0),x.right0+y.left0)
});
}
inline void put_down(ll id,ll type)
{
if(type<=2)
{
if(type==1)
tr[id]=node({0,tr[id].len,0,tr[id].len,0,tr[id].len,0,tr[id].len,0,0,tr[id].lt,tr[id].rt,tr[id].len});
else
{
node x={tr[id].len,0,tr[id].len,0,tr[id].len,0,tr[id].len,0,1,0,tr[id].lt,tr[id].rt,tr[id].len};
tr[id]=x;
}
}
if(type==3)
tr[id].lazy_q^=1,swap(tr[id].num0,tr[id].num1),
swap(tr[id].left0,tr[id].left1),swap(tr[id].right0,tr[id].right1),
swap(tr[id].mid0,tr[id].mid1);
}
inline void build(ll l,ll r,ll id)
{
tr[id].len=r-l+1;
tr[id].lt=l;
tr[id].rt=r;
tr[id].lazy_f=-1;
if(l==r)
{
if(a[l]==1)
tr[id].num1=tr[id].left1=tr[id].right1=tr[id].mid1=1;
else
tr[id].num0=tr[id].left0=tr[id].right0=tr[id].mid0=1;
return void();
}
ll mid=(l+r)>>1;
build(l,mid,lson(id));
build(mid+1,r,rson(id));
tr[id].num1=tr[lson(id)].num1+tr[rson(id)].num1;
tr[id].num0=tr[lson(id)].num0+tr[rson(id)].num0;
tr[id].left1=(tr[lson(id)].num0?tr[lson(id)].left1:tr[lson(id)].num1+tr[rson(id)].left1);
tr[id].left0=(tr[lson(id)].num1?tr[lson(id)].left0:tr[lson(id)].num0+tr[rson(id)].left0);
tr[id].right1=(tr[rson(id)].num0?tr[rson(id)].right1:tr[rson(id)].num1+tr[lson(id)].right1);
tr[id].right0=(tr[rson(id)].num1?tr[rson(id)].right0:tr[rson(id)].num0+tr[lson(id)].right0);
tr[id].mid1=max(max(tr[lson(id)].mid1,tr[rson(id)].mid1),tr[lson(id)].right1+tr[rson(id)].left1);
tr[id].mid0=max(max(tr[lson(id)].mid0,tr[rson(id)].mid0),tr[lson(id)].right0+tr[rson(id)].left0);
}
inline void push_down(ll id)
{
if(tr[id].lazy_f!=-1)
put_down(lson(id),tr[id].lazy_f+1),
put_down(rson(id),tr[id].lazy_f+1);
if(tr[id].lazy_q)
put_down(lson(id),3),
put_down(rson(id),3);
tr[id].lazy_f=-1;
tr[id].lazy_q=0;
}
inline void change(ll l,ll r,ll id,ll tp)
{
push_down(id);
if(r<tr[id].lt || l>tr[id].rt)
return void();
if(l<=tr[id].lt && r>=tr[id].rt)
{
put_down(id,tp);
return void();
}
change(l,r,lson(id),tp);
change(l,r,rson(id),tp);
tr[id].num1=tr[lson(id)].num1+tr[rson(id)].num1;
tr[id].num0=tr[lson(id)].num0+tr[rson(id)].num0;
tr[id].left1=(tr[lson(id)].num0?tr[lson(id)].left1:tr[lson(id)].num1+tr[rson(id)].left1);
tr[id].left0=(tr[lson(id)].num1?tr[lson(id)].left0:tr[lson(id)].num0+tr[rson(id)].left0);
tr[id].right1=(tr[rson(id)].num0?tr[rson(id)].right1:tr[rson(id)].num1+tr[lson(id)].right1);
tr[id].right0=(tr[rson(id)].num1?tr[rson(id)].right0:tr[rson(id)].num0+tr[lson(id)].right0);
tr[id].mid1=max(max(tr[lson(id)].mid1,tr[rson(id)].mid1),tr[lson(id)].right1+tr[rson(id)].left1);
tr[id].mid0=max(max(tr[lson(id)].mid0,tr[rson(id)].mid0),tr[lson(id)].right0+tr[rson(id)].left0);
}
inline node query(ll l,ll r,ll id)
{
push_down(id);
if(r<tr[id].lt || l>tr[id].rt)
return node({0,0,0,0,0,0,0,0,0,0,0,0,0});
if(tr[id].lt>=l && tr[id].rt<=r)
return tr[id];
return merge(query(l,r,lson(id)),query(l,r,rson(id)));
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while(m--)
{
ll opt,l,r;
cin>>opt>>l>>r;
opt++;l++;r++;
if(opt==4)
cout<<query(l,r,1).num1<<endl;
else if(opt==5)
{
node tmp=query(l,r,1);
cout<<tmp.mid1<<endl;
} else change(l,r,1,opt);
}
return 0;
}代码太长，见谅
by z_yq @ 2024-06-27 08:48:41
想看有调试语句的代码，在这里：
#include<bits/stdc++.h>
#define ll long long
#define lson(x) x<<1
#define rson(x) x<<1|1
using namespace std;
const ll N=1e5+9;
struct node
{
ll num1,num0;
ll left1,left0,right1,right0;
ll mid1,mid0;
ll lazy_f,lazy_q,lt,rt,len; //lazy_f 赋值标记(-1) lazy_q 取反标记(0)
}tr[N*4];
ll n,m,a[N];
inline node merge(node x,node y)
{
return node({
x.num1+y.num1,
x.num0+y.num0,
(x.num0?x.left1:x.num1+y.left1),
(x.num1?x.left0:x.num0+y.left0),
(y.num0?y.left1:y.num1+x.left1),
(y.num1?y.left0:y.num0+x.left0),
max(max(x.mid1,y.mid1),x.right1+y.left1),
max(max(x.mid0,y.mid0),x.right0+y.left0)
});
}
inline void put_down(ll id,ll type)
{
if(type<=2)
{
if(type==1)
tr[id]=node({0,tr[id].len,0,tr[id].len,0,tr[id].len,0,tr[id].len,0,0,tr[id].lt,tr[id].rt,tr[id].len});
else
{
node x={tr[id].len,0,tr[id].len,0,tr[id].len,0,tr[id].len,0,1,0,tr[id].lt,tr[id].rt,tr[id].len};
tr[id]=x;
}
}
if(type==3)
tr[id].lazy_q^=1,swap(tr[id].num0,tr[id].num1),
swap(tr[id].left0,tr[id].left1),swap(tr[id].right0,tr[id].right1),
swap(tr[id].mid0,tr[id].mid1);
}
inline void build(ll l,ll r,ll id)
{
// cout<<"build:\n";
// cout<<id<<' '<<l<<' '<<r<<endl;
tr[id].len=r-l+1;
tr[id].lt=l;
tr[id].rt=r;
tr[id].lazy_f=-1;
if(l==r)
{
if(a[l]==1)
tr[id].num1=tr[id].left1=tr[id].right1=tr[id].mid1=1;
else
tr[id].num0=tr[id].left0=tr[id].right0=tr[id].mid0=1;
return void();
}
ll mid=(l+r)>>1;
build(l,mid,lson(id));
build(mid+1,r,rson(id));
tr[id].num1=tr[lson(id)].num1+tr[rson(id)].num1;
tr[id].num0=tr[lson(id)].num0+tr[rson(id)].num0;
tr[id].left1=(tr[lson(id)].num0?tr[lson(id)].left1:tr[lson(id)].num1+tr[rson(id)].left1);
tr[id].left0=(tr[lson(id)].num1?tr[lson(id)].left0:tr[lson(id)].num0+tr[rson(id)].left0);
tr[id].right1=(tr[rson(id)].num0?tr[rson(id)].right1:tr[rson(id)].num1+tr[lson(id)].right1);
tr[id].right0=(tr[rson(id)].num1?tr[rson(id)].right0:tr[rson(id)].num0+tr[lson(id)].right0);
tr[id].mid1=max(max(tr[lson(id)].mid1,tr[rson(id)].mid1),tr[lson(id)].right1+tr[rson(id)].left1);
tr[id].mid0=max(max(tr[lson(id)].mid0,tr[rson(id)].mid0),tr[lson(id)].right0+tr[rson(id)].left0);
}
inline void push_down(ll id)
{
if(tr[id].lazy_f!=-1)
put_down(lson(id),tr[id].lazy_f+1),
put_down(rson(id),tr[id].lazy_f+1);
if(tr[id].lazy_q)
put_down(lson(id),3),
put_down(rson(id),3);
tr[id].lazy_f=-1;
tr[id].lazy_q=0;
}
inline void change(ll l,ll r,ll id,ll tp)
{
push_down(id);
if(r<tr[id].lt || l>tr[id].rt)
return void();
// cout<<id<<' '<<tr[id].lt<<' '<<tr[id].rt<<' '<<l<<' '<<r<<endl;
if(l<=tr[id].lt && r>=tr[id].rt)
{
put_down(id,tp);
return void();
}
change(l,r,lson(id),tp);
change(l,r,rson(id),tp);
tr[id].num1=tr[lson(id)].num1+tr[rson(id)].num1;
tr[id].num0=tr[lson(id)].num0+tr[rson(id)].num0;
tr[id].left1=(tr[lson(id)].num0?tr[lson(id)].left1:tr[lson(id)].num1+tr[rson(id)].left1);
tr[id].left0=(tr[lson(id)].num1?tr[lson(id)].left0:tr[lson(id)].num0+tr[rson(id)].left0);
tr[id].right1=(tr[rson(id)].num0?tr[rson(id)].right1:tr[rson(id)].num1+tr[lson(id)].right1);
tr[id].right0=(tr[rson(id)].num1?tr[rson(id)].right0:tr[rson(id)].num0+tr[lson(id)].right0);
tr[id].mid1=max(max(tr[lson(id)].mid1,tr[rson(id)].mid1),tr[lson(id)].right1+tr[rson(id)].left1);
tr[id].mid0=max(max(tr[lson(id)].mid0,tr[rson(id)].mid0),tr[lson(id)].right0+tr[rson(id)].left0);
}
inline node query(ll l,ll r,ll id)
{
push_down(id);
if(r<tr[id].lt || l>tr[id].rt)
return node({0,0,0,0,0,0,0,0,0,0,0,0,0});
if(tr[id].lt>=l && tr[id].rt<=r)
return tr[id];
return merge(query(l,r,lson(id)),query(l,r,rson(id)));
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
/*
cout<<endl;
for(int i=1;i<=n*4;i++)
if(tr[i].len!=0)
{
cout<<"id:"<<i<<' '<<tr[i].lt<<' '<<tr[i].rt<<endl;
cout<<tr[i].left0<<' '<<tr[i].left1<<endl;
cout<<tr[i].mid0<<' '<<tr[i].mid1<<endl;
cout<<tr[i].right0<<' '<<tr[i].right1<<endl;
cout<<"---\n"<<tr[i].lazy_f<<' '<<tr[i].lazy_q<<endl;
cout<<endl;
}
// */
while(m--)
{
ll opt,l,r;
cin>>opt>>l>>r;
opt++;l++;r++;
if(opt==4)
cout<<query(l,r,1).num1<<endl;
else if(opt==5)
{
node tmp=query(l,r,1);
cout<<tmp.mid1<<endl;
} else change(l,r,1,opt);
/*
cout<<endl;
for(int i=1;i<=n*4;i++)
if(tr[i].len!=0)
{
cout<<"id:"<<i<<' '<<tr[i].lt<<' '<<tr[i].rt<<endl;
cout<<tr[i].left0<<' '<<tr[i].left1<<endl;
cout<<tr[i].mid0<<' '<<tr[i].mid1<<endl;
cout<<tr[i].right0<<' '<<tr[i].right1<<endl;
cout<<"---\n"<<tr[i].lazy_f<<' '<<tr[i].lazy_q<<endl;
cout<<endl;
}
// */
}
return 0;
}by __Sam__ @ 2024-06-27 19:39:35
@Zachary_zhong 代码这么长，有人会修改（除了你自己）就是出神入化的那种。
by z_yq @ 2024-06-27 22:48:41
@Sam 我找人帮忙改有问题了是吧，不能好好讲话吗？
by __Sam__ @ 2024-06-28 05:53:59
@Zachary_zhong 调侃一下，真不会开玩笑
by z_yq @ 2024-06-28 07:57:17
@Sam 哦，好的，对不起