Naszt @ 2024-10-09 12:28:22
如题，这玩意效率不是应该超高的吗？
link
#include<bits/stdc++.h>
typedef unsigned int i4;
const i4 MX=1000005<<2;
i4 n,m,N,D,cls[MX],flip[MX];
struct Node{i4 s0,s1,m0,m1,l0,l1,r0,r1;}A[MX];
Node operator+(const Node x,const Node y){
return {x.s0+y.s0,x.s1+y.s1,
std::max(std::max(x.m0,y.m0),x.r0+y.l0),
std::max(std::max(x.m1,y.m1),x.r1+y.l1),
x.l0+(x.s1?0:y.l0),x.l1+(x.s0?0:y.l1),
y.r0+(y.s1?0:x.r0),y.r1+(y.s0?0:x.r1)};
}void pup(i4 x){A[x]=A[x<<1]+A[x<<1|1];}
void upd(i4 x,const i4 cl,const i4 fl){
Node&X=A[x];
if(cl<2){const i4 l=cl*(X.s0+X.s1),r=(!cl)*(X.s0+X.s1);
X={r,l,r,l,r,l,r,l},cls[x]=cl,flip[x]=0;
}if(fl)std::swap(X.s0,X.s1),std::swap(X.m0,X.m1),
std::swap(X.l0,X.l1),std::swap(X.r0,X.r1),flip[x]^=1;
}void pdn(i4 x){
upd(x<<1,cls[x],flip[x]),upd(x<<1|1,cls[x],flip[x]);
cls[x]=2,flip[x]=0;
}void push(i4 l,i4 r){for(i4 i=D;i;i--)pdn(l>>i),pdn(r>>i);}
void mdf(i4 l,i4 r,const i4 cl,const i4 fl){
for(push(l+=N-1,r+=N+1);l^r^1;pup(l>>=1),pup(r>>=1)){
if(~l&1)upd(l^1,cl,fl);if(r&1)upd(r^1,cl,fl);
}while(l>>=1)pup(l);
}Node que(i4 l,i4 r){
Node L,R;L=R={0,0,0,0,0,0,0,0};
for(push(l+=N-1,r+=N+1);l^r^1;l>>=1,r>>=1){
if(~l&1)L=L+A[l^1];if(r&1)R=A[r^1]+R;
}return L+R;
}int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0),std::cout.tie(0);
std::cin>>n>>m;N=1<<(D=std::__lg(n+1)+1);
for(i4 i=N+1,x;i<=N+n;i++)
std::cin>>x,A[i]={!x,x,!x,x,!x,x,!x,x},cls[i]=2;
for(i4 i=N-1;i;i--)pup(i),cls[i]=2;
while(m--){i4 op,x,y;std::cin>>op>>x>>y;++x;++y;
if(op<3){mdf(x,y,op,op==2);continue;}
Node X=que(x,y);std::cout<<(op==3?X.s1:X.m1)<<"\n";
}return 0;
}by Gcc_Gdb_7_8_1 @ 2024-10-09 12:55:43
@Naszt 马蜂差评...
by Naszt @ 2024-10-09 17:14:58
加了个 inline，卡到了最优解
#include<bits/stdc++.h>
typedef unsigned int i4;
char buf[1<<21],*p1=buf,pbuf[1<<21],*pp=pbuf;
inline i4&in(i4&x){while(!isdigit(*p1++));x=*(p1-1)^48;
while(isdigit(*p1))x=x*10+((*p1++)^48);return x;
}inline void out(uint64_t x){
static char s[20];i4 t=0;do s[t++]=x%10,x/=10;while(x);
while(t)*pp++=s[--t]^48;*pp++=10;
}const i4 MX=100005<<2;
i4 n,m,N,D,cls[MX],flip[MX];
struct Node{i4 s0,s1,m0,m1,l0,l1,r0,r1;}A[MX];
inline Node operator+(const Node x,const Node y){
return {x.s0+y.s0,x.s1+y.s1,
std::max(std::max(x.m0,y.m0),x.r0+y.l0),
std::max(std::max(x.m1,y.m1),x.r1+y.l1),
x.l0+(x.s1?0:y.l0),x.l1+(x.s0?0:y.l1),
y.r0+(y.s1?0:x.r0),y.r1+(y.s0?0:x.r1)};
}inline void pup(i4 x){A[x]=A[x<<1]+A[x<<1|1];}
inline void upd(i4 x,const i4 cl,const i4 fl){
Node&X=A[x];
if(cl<2){const i4 l=cl*(X.s0+X.s1),r=(!cl)*(X.s0+X.s1);
X={r,l,r,l,r,l,r,l},cls[x]=cl,flip[x]=0;
}if(fl)std::swap(X.s0,X.s1),std::swap(X.m0,X.m1),
std::swap(X.l0,X.l1),std::swap(X.r0,X.r1),flip[x]^=1;
}inline void pdn(i4 x){
upd(x<<1,cls[x],flip[x]),upd(x<<1|1,cls[x],flip[x]);
cls[x]=2,flip[x]=0;
}inline void push(i4 l,i4 r){for(i4 i=D;i;i--)pdn(l>>i),pdn(r>>i);}
inline void mdf(i4 l,i4 r,const i4 cl,const i4 fl){
for(push(l+=N-1,r+=N+1);l^r^1;pup(l>>=1),pup(r>>=1)){
if(~l&1)upd(l^1,cl,fl);if(r&1)upd(r^1,cl,fl);
}while(l>>=1)pup(l);
}inline Node que(i4 l,i4 r){
Node L,R;L=R={0,0,0,0,0,0,0,0};
for(push(l+=N-1,r+=N+1);l^r^1;l>>=1,r>>=1){
if(~l&1)L=L+A[l^1];if(r&1)R=A[r^1]+R;
}return L+R;
}int main(){
fread(buf,1,1<<21,stdin);
N=1<<(D=std::__lg(in(n)+1)+1),in(m);
for(i4 i=N+1,x;i<=N+n;i++)
in(x),A[i]={!x,x,!x,x,!x,x,!x,x},cls[i]=2;
for(i4 i=N-1;i;i--)pup(i),cls[i]=2;
while(m--){i4 op,x,y;in(op),in(x)++,in(y)++;
if(op<3){mdf(x,y,op,op==2);continue;}
Node X=que(x,y);out(op==3?X.s1:X.m1);
}fwrite(pbuf,1,pp-pbuf,stdout);
return 0;
}望周知
by Xeffry @ 2024-10-11 21:42:36
@Gcc_Gdb_7_8_1 骂的好
by LLVM_lldb_14_0_0 @ 2024-10-12 12:47:26
@Xeffry emmm
by blue_demon @ 2024-10-13 21:37:23
@Gcc_Gdb_7_8_1 骂得好
by Gcc_Gdb_7_8_1 @ 2024-10-13 21:39:29
@blue_demon emmm * 2
by DReamwastaken__ @ 2024-10-13 21:44:18
@Gcc_Gdb_7_8_1 骂得好 * 3
by Naszt @ 2024-10-17 23:39:27
@Gcc_Gdb_7_8_1 @Xeffry @blue_demon @DReamwastaken__
就是说啊，有没有一种可能，我其实是个抖 M
（尖叫）（扭曲）（阴暗的爬行） （爬行）（扭动）（尖叫）（扭曲）（阴暗的爬行） （爬行）（扭动）（尖叫）（扭曲）（阴暗的爬行） （爬行）（扭动）
by blue_demon @ 2024-10-18 20:57:03
@Naszt 学姐逆天了
by Delete_error @ 2024-10-21 21:48:09
好恐怖的码疯