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 Hexarhy @ 2020-04-04 20:21:00
这么长的代码两个注释都没有怎么看差评
by lndjy @ 2020-04-04 20:21:45
1.在这个蒟蒻都切Ynoi的时代,我确实是新人
2.我确实WA爆零了
by HoshiuZ @ 2020-04-04 20:31:54
@水题淹死的鱼 父节点为lazy值为2时,标记下传时其子节点的标记情况也要分类讨论吧qwq
by HoshiuZ @ 2020-04-04 20:32:51
@水题淹死的鱼 你和我当时思路差不多,都是把标记放在一起的qwq
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,m,op,l,r,tot=0;
struct node{
int l,r,maxn1,lmaxn1,rmaxn1,maxn0,lmaxn0,rmaxn0,lazy,sum;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define m1(x) tree[x].maxn1
#define lm1(x) tree[x].lmaxn1
#define rm1(x) tree[x].rmaxn1
#define m0(x) tree[x].maxn0
#define lm0(x) tree[x].lmaxn0
#define rm0(x) tree[x].rmaxn0
#define lazy(x) tree[x].lazy
#define s(x) tree[x].sum
#define ls p<<1
#define rs p<<1|1
}tree[N<<2];
void push_up(int p) {
s(p)=s(ls)+s(rs);
m1(p)=max(rm1(ls)+lm1(rs),max(m1(ls),m1(rs)));
m0(p)=max(rm0(ls)+lm0(rs),max(m0(ls),m0(rs)));
if(lm1(ls)==r(ls)-l(ls)+1) lm1(p)=lm1(ls)+lm1(rs);
else lm1(p)=lm1(ls);
if(rm1(rs)==r(rs)-l(rs)+1) rm1(p)=rm1(rs)+rm1(ls);
else rm1(p)=rm1(rs);
if(lm0(ls)==r(ls)-l(ls)+1) lm0(p)=lm0(ls)+lm0(rs);
else lm0(p)=lm0(ls);
if(rm0(rs)==r(rs)-l(rs)+1) rm0(p)=rm0(rs)+rm0(ls);
else rm0(p)=rm0(rs);
}
void build(int p,int l,int r) {
l(p)=l,r(p)=r;
if(l==r) {
scanf("%d",&s(p));
lm1(p)=rm1(p)=m1(p)=s(p);
lm0(p)=rm0(p)=m0(p)=s(p)^1;
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(p);
}
void spread(int p) {
if(!lazy(p)) return ;
if(lazy(p)==1) {
s(ls)=s(rs)=0;
m1(ls)=lm1(ls)=rm1(ls)=0;
m0(ls)=lm0(ls)=rm0(ls)=r(ls)-l(ls)+1;
m1(rs)=lm1(rs)=rm1(rs)=0;
m0(rs)=lm0(rs)=rm0(rs)=r(rs)-l(rs)+1;
lazy(ls)=1,lazy(rs)=1;
lazy(p)=0;
}
if(lazy(p)==2) {
s(ls)=r(ls)-l(ls)+1;
s(rs)=r(rs)-l(rs)+1;
m1(ls)=lm1(ls)=rm1(ls)=r(ls)-l(ls)+1;
m0(ls)=lm0(ls)=rm0(ls)=0;
m1(rs)=lm1(rs)=rm1(rs)=r(rs)-l(rs)+1;
m0(rs)=lm0(rs)=rm0(rs)=0;
lazy(ls)=2,lazy(rs)=2;
lazy(p)=0;
}
if(lazy(p)==3) {
s(ls)=r(ls)-l(ls)+1-s(ls);
s(rs)=r(rs)-l(rs)+1-s(rs);
swap(m1(ls),m0(ls)),swap(m1(rs),m0(rs));
swap(lm1(ls),lm0(ls)),swap(lm1(rs),lm0(rs));
swap(rm1(ls),rm0(ls)),swap(rm1(rs),rm0(rs));
if(!lazy(ls)) lazy(ls)=3;
else if(lazy(ls)==1) lazy(ls)=2;
else if(lazy(ls)==2) lazy(ls)=1;
else lazy(ls)=0;
if(!lazy(rs)) lazy(rs)=3;
else if(lazy(rs)==1) lazy(rs)=2;
else if(lazy(rs)==2) lazy(rs)=1;
else lazy(rs)=0;
lazy(p)=0;
}
}
void change(int p,int l,int r,int x) {
if(l(p)>r||r(p)<l) return ;
spread(p);
if(l(p)>=l&&r(p)<=r) {
if(!x) {
s(p)=0;
m1(p)=lm1(p)=rm1(p)=0;
m0(p)=lm0(p)=rm0(p)=r(p)-l(p)+1;
lazy(p)=1;
return ;
}
else if(x==1) {
s(p)=r(p)-l(p)+1;
m1(p)=lm1(p)=rm1(p)=r(p)-l(p)+1;
m0(p)=lm0(p)=rm0(p)=0;
lazy(p)=2;
return ;
}
else {
s(p)=r(p)-l(p)+1-s(p);
swap(m1(p),m0(p));
swap(lm1(p),lm0(p));
swap(rm1(p),rm0(p));
lazy(p)=3;
return ;
}
}
change(ls,l,r,x);
change(rs,l,r,x);
push_up(p);
}
int ask(int p,int l,int r,int op) {
if(op==3) {
if(l(p)>r||r(p)<l) return 0;
if(l(p)>=l&&r(p)<=r) {
return s(p);
}
spread(p);
return ask(ls,l,r,op)+ask(rs,l,r,op);
}
else {
if(l(p)>r||r(p)<l) return 0;
if(l(p)>=l&&r(p)<=r) return m1(p);
spread(p);
return max(max(ask(ls,l,r,op),ask(rs,l,r,op)),min(rm1(ls),r(ls)-l+1)+min(lm1(rs),r-l(rs)+1));
}
}
int main() {
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&op,&l,&r);
l++,r++;
if(op<=2) change(1,l,r,op);
else printf("%d\n",ask(1,l,r,op));
}
return 0;
}
by lndjy @ 2020-04-04 20:33:20
@Yuzuriha_Inori 谢谢大佬,我sb了
by JRzyh @ 2020-04-06 15:18:19
本地没有AC
IEE