lndjy @ 2020-04-04 20:16:25
样例过了提交爆零WA:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int amax,lmax,rmax;
int len;
};
int inline read()
{
int ans=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans*f;
}
struct tree
{
int l,r;
int len;
int sum,lmax[2],rmax[2],amax[2];
int lazy;
}t[400005];
int n,m,a[100005];
void pushup(int k)
{
t[k].sum=t[k*2].sum+t[k*2+1].sum;
for(int i=0;i<=1;i++)
{
t[k].lmax[i]=(t[k*2].lmax[i]==t[k*2].len?t[k*2].lmax[i]+t[k*2+1].lmax[i]:t[k*2].lmax[i]);
t[k].rmax[i]=(t[k*2+1].rmax[i]==t[k*2+1].len?t[k*2+1].rmax[i]+t[k*2].rmax[i]:t[k*2+1].rmax[i]);
t[k].amax[i]=max(t[k*2].amax[i],max(t[k*2+1].amax[i],t[k*2].rmax[i]+t[k*2+1].lmax[i]));
}
}
void pushdown(int k)
{
if(t[k].lazy==0)
{
t[k*2].sum=t[k*2].lmax[1]=t[k*2].rmax[1]=t[k*2].amax[1]=t[k*2].lazy=0;
t[k*2+1].sum=t[k*2+1].lmax[1]=t[k*2+1].rmax[1]=t[k*2+1].amax[1]=t[k*2+1].lazy=0;
t[k*2].lmax[0]=t[k*2].rmax[0]=t[k*2].amax[0]=t[k*2].len;
t[k*2+1].lmax[0]=t[k*2+1].rmax[0]=t[k*2+1].amax[0]=t[k*2+1].len;
}
if(t[k].lazy==1)
{
t[k*2].sum=t[k*2].amax[1]=t[k*2].lmax[1]=t[k*2].rmax[1]=t[k*2].len;
t[k*2+1].sum=t[k*2+1].amax[1]=t[k*2+1].lmax[1]=t[k*2+1].rmax[1]=t[k*2+1].len;
t[k*2].lazy=t[k*2+1].lazy=1;
t[k*2].lmax[0]=t[k*2].rmax[0]=t[k*2].amax[0]=0;
t[k*2+1].lmax[0]=t[k*2+1].rmax[0]=t[k*2+1].amax[0]=0;
}
if(t[k].lazy==2)
{
t[k*2].sum=t[k*2].len-t[k*2].sum;
t[k*2+1].sum=t[k*2+1].len-t[k*2+1].sum;
t[k*2].lazy=t[k*2+1].lazy=2;
swap(t[k*2].lmax[0],t[k*2].lmax[1]);swap(t[k*2].rmax[0],t[k*2].rmax[1]);swap(t[k*2].amax[0],t[k*2].amax[1]);
swap(t[k*2+1].lmax[0],t[k*2+1].lmax[1]);swap(t[k*2+1].rmax[0],t[k*2+1].rmax[1]);swap(t[k*2+1].amax[0],t[k*2+1].amax[1]);
}
t[k].lazy=-1;
}
void build(int l,int r,int k)
{
t[k].l=l;t[k].r=r;t[k].len=r-l+1;
t[k].lazy=-1;
if(l==r)
{
t[k].sum=a[l];
t[k].lmax[a[l]]=t[k].rmax[a[l]]=t[k].amax[a[l]]=1;
return;
}
int mid=(l+r)/2;
build(l,mid,k*2);
build(mid+1,r,k*2+1);
pushup(k);
}
void change(int l,int r,int k,int v)
{
if(l<=t[k].l&&t[k].r<=r)
{
if(v==0) t[k].sum=0;
else t[k].sum=t[k].len;
t[k].lazy=v;
t[k].lmax[v]=t[k].rmax[v]=t[k].amax[v]=t[k].len;
t[k].lmax[!v]=t[k].rmax[!v]=t[k].amax[!v]=0;
return;
}
pushdown(k);
if(t[k*2].r>=l)
change(l,r,k*2,v);
if(t[k*2+1].l<=r)
change(l,r,k*2+1,v);
pushup(k);
}
void no(int l,int r,int k)
{
if(l<=t[k].l&&t[k].r<=r)
{
t[k].sum=t[k].len-t[k].sum;
swap(t[k].lmax[0],t[k].lmax[1]);swap(t[k].rmax[0],t[k].rmax[1]);swap(t[k].amax[0],t[k].amax[1]);
if(t[k].lazy==2) t[k].lazy=-1;
else if(t[k].lazy==-1) t[k].lazy=2;
else if(t[k].lazy==1) t[k].lazy=0;
else t[k].lazy=1;
return;
}
pushdown(k);
if(t[k*2].r>=l)
no(l,r,k*2);
if(t[k*2+1].l<=r)
no(l,r,k*2+1);
pushup(k);
}
int ask(int l,int r,int k)
{
if(l<=t[k].l&&t[k].r<=r)
return t[k].sum;
pushdown(k);
int ans=0;
if(t[k*2].r>=l)
ans+=ask(l,r,k*2);
if(t[k*2+1].l<=r)
ans+=ask(l,r,k*2+1);
return ans;
}
node askmax(int l,int r,int k)
{
pushdown(k);
if(l==t[k].l&&r==t[k].r)
return (node){t[k].amax[1],t[k].lmax[1],t[k].rmax[1],t[k].len};
if(t[k*2].r>=r) return askmax(l,r,k*2);
if(t[k*2+1].l<=l) return askmax(l,r,k*2+1);
node ans=(node){0,0,0,0};
node a=askmax(l,t[k*2].r,k*2),b=askmax(t[k*2+1].l,r,k*2+1);
if(a.lmax==a.len) ans.lmax=a.lmax+b.lmax;
else ans.lmax=a.lmax;
if(b.rmax==b.len) ans.rmax=a.rmax+b.rmax;
else ans.rmax=b.rmax;
ans.len=a.len+b.len;
ans.amax=max(a.amax,max(b.amax,a.rmax+b.lmax));
return ans;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
build(1,n,1);
for(int i=1;i<=m;i++)
{
int op=read(),l=read()+1,r=read()+1;
if(op<=1) change(l,r,1,op);
if(op==2) no(l,r,1);
if(op==3) cout<<ask(l,r,1)<<'\n';
if(op==4) cout<<askmax(l,r,1).amax<<'\n';
}
return 0;
}
by 听取MLE声一片 @ 2020-04-04 20:16:37
前排
by Wenoide @ 2020-04-04 20:17:19
这种题还是不要问了吧……应该不会有人耐心看的
by lndjy @ 2020-04-04 20:17:19
@听取mc声一片 求助帖你抢个毛线前排
by Spasmodic @ 2020-04-04 20:17:42
QNDXR
by Eon_Sky @ 2020-04-04 20:17:52
QNDXR
by UnyieldingTrilobite @ 2020-04-04 20:18:54
btd危
by IntrepidStrayer @ 2020-04-04 20:19:03
抱灵++
by Custlo0793 @ 2020-04-04 20:19:29
话说泥萌这群抄袭神帖的有什么NB
by lndjy @ 2020-04-04 20:19:43
@happydef 现在蒟蒻都切Ynoi了,没有办法啊
by YUYGFGG @ 2020-04-04 20:20:48
你不说我都快忘了这个神贴