样例和hack过了,其他全WA。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int res = 0,f = 1;
char ch = getchar();
while (ch<'0'||ch>'9') f = (ch=='-'?-1:1),ch = getchar();
while (ch>='0'&&ch<='9') res = (res<<3)+(res<<1)+(ch^48),ch = getchar();
return res*f;
}
void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>9) write(x/10);
putchar(x%10+'0');
}
void writech(int x,char ch){write(x),putchar(ch);}
const int N = 1e5+5;
int n,m;
int a[N];
struct tree
{
int l,r;
int sum,lm[2],rm[2],qm[2];
int rev,cover;
}tr[4*N];
void pushup(int x)
{
tr[x].sum=tr[2*x].sum+tr[2*x+1].sum;
tr[x].lm[1]=tr[2*x].lm[1]+(tr[2*x].qm[0]==0)*tr[2*x+1].lm[1];
tr[x].rm[1]=tr[2*x+1].rm[1]+(tr[2*x+1].qm[0]==0)*tr[2*x].rm[1];
tr[x].qm[1]=max(max(tr[2*x].qm[1],tr[2*x+1].qm[1]),tr[2*x].rm[1]+tr[2*x+1].lm[1]);
tr[x].lm[0]=tr[2*x].lm[0]+(tr[2*x].qm[1]==0)*tr[2*x+1].lm[0];
tr[x].rm[0]=tr[2*x+1].rm[0]+(tr[2*x+1].qm[1]==0)*tr[2*x].rm[0];
tr[x].qm[0]=max(max(tr[2*x].qm[0],tr[2*x+1].qm[0]),tr[2*x].rm[0]+tr[2*x+1].lm[0]);
}
void bt(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;
tr[x].rev=0;
tr[x].cover=-1;
if (l==r)
{
tr[x].sum=0;
tr[x].lm[1]=tr[x].lm[0]=0;
tr[x].rm[1]=tr[x].rm[0]=0;
tr[x].qm[1]=tr[x].qm[0]=0;
if (a[l]==1) tr[x].sum=tr[x].lm[1]=tr[x].rm[1]=tr[x].qm[1]=1;
else tr[x].lm[0]=tr[x].rm[0]=tr[x].qm[0]=1;
return ;
}
int mid = (l+r)/2;
bt(2*x,l,mid);
bt(2*x+1,mid+1,r);
pushup(x);
}
void pushdown(int x)
{
if (tr[x].cover!=-1)
{
int s = tr[x].cover;
tr[2*x].sum=(tr[2*x].r-tr[2*x].l+1)*s;
tr[2*x+1].sum=(tr[2*x+1].r-tr[2*x+1].l+1)*s;
tr[2*x].cover=tr[2*x+1].cover=s;
tr[2*x].rev=tr[2*x+1].rev=0;
tr[2*x].lm[s]=tr[2*x].rm[s]=tr[2*x].qm[s]=tr[2*x].r-tr[2*x].l+1;
tr[2*x+1].lm[s]=tr[2*x+1].rm[s]=tr[2*x+1].qm[s]=tr[2*x+1].r-tr[2*x+1].l+1;
s^=1;
tr[2*x].lm[s]=tr[2*x].rm[s]=tr[2*x].qm[s]=0;
tr[2*x+1].lm[s]=tr[2*x+1].rm[s]=tr[2*x+1].qm[s]=0;
tr[x].cover=-1;
}
if (tr[x].rev)
{
tr[2*x].sum=tr[2*x].r-tr[2*x].l+1-tr[2*x].sum;
tr[2*x+1].sum=tr[2*x+1].r-tr[2*x+1].l+1-tr[2*x+1].sum;
if (tr[2*x].cover!=-1) tr[2*x].cover^=1;
if (tr[2*x+1].cover!=-1) tr[2*x+1].cover^=1;
tr[2*x].rev^=1,tr[2*x+1].rev^=1;
swap(tr[2*x].lm[1],tr[2*x].lm[0]);
swap(tr[2*x].rm[1],tr[2*x].rm[0]);
swap(tr[2*x].qm[1],tr[2*x].qm[0]);
swap(tr[2*x+1].lm[1],tr[2*x+1].lm[0]);
swap(tr[2*x+1].rm[1],tr[2*x+1].rm[0]);
swap(tr[2*x+1].qm[1],tr[2*x+1].qm[0]);
tr[x].rev^=1;
}
}
void mod(int x,int ql,int qr,int v)
{
int l = tr[x].l,r = tr[x].r;
if (ql<=l&&r<=qr)
{
tr[x].sum=(r-l+1)*v;
tr[x].lm[v]=tr[x].rm[v]=tr[x].qm[v]=r-l+1;
tr[x].lm[v^1]=tr[x].rm[v^1]=tr[x].qm[v^1]=0;
tr[x].cover=v;
tr[x].rev=0;
return ;
}
pushdown(x);
int mid = (l+r)/2;
if (ql<=mid) mod(2*x,ql,qr,v);
if (qr>mid) mod(2*x+1,ql,qr,v);
pushup(x);
}
void revers(int x,int ql,int qr)
{
int l = tr[x].l,r = tr[x].r;
if (ql<=l&&r<=qr)
{
tr[x].sum=r-l+1-tr[x].sum;
swap(tr[x].lm[1],tr[x].lm[0]);
swap(tr[x].rm[1],tr[x].rm[0]);
swap(tr[x].qm[1],tr[x].qm[0]);
if (tr[x].cover!=-1) tr[x].cover^=1;
else tr[x].rev^=1;
return ;
}
pushdown(x);
int mid = (l+r)/2;
if (ql<=mid) revers(2*x,ql,qr);
if (qr>mid) revers(2*x+1,ql,qr);
pushup(x);
}
int query1(int x,int ql,int qr)
{
int l = tr[x].l,r = tr[x].r;
if (ql<=l&&r<=qr) return tr[x].sum;
pushdown(x);
int mid = (l+r)/2;
int res = 0;
if (ql<=mid) res+=query1(2*x,ql,qr);
if (qr>mid) res+=query1(2*x+1,ql,qr);
return res;
}
tree query2(int x,int ql,int qr)
{
int l = tr[x].l,r = tr[x].r;
if (ql<=l&&r<=qr) return tr[x];
tree ll,rr;
bool hl=false,hr=false;
int mid = (l+r)/2;
if (ql<=mid)
{
ll=query2(2*x,ql,qr);
hl=true;
}
if (qr>mid)
{
rr=query2(2*x+1,ql,qr);
hr=true;
}
if (hl&&hr)
{
tree res;
res.l=ll.l,res.r=rr.r;
res.sum=ll.sum+rr.sum;
res.lm[1]=ll.lm[1]+(ll.qm[0]==0)*rr.lm[1];
res.rm[1]=rr.rm[1]+(rr.qm[0]==0)*ll.rm[1];
res.qm[1]=max(max(ll.qm[1],rr.qm[1]),ll.rm[1]+rr.lm[1]);
res.lm[0]=ll.lm[0]+(ll.qm[1]==0)*rr.lm[0];
res.rm[0]=rr.rm[0]+(rr.qm[1]==0)*ll.rm[0];
res.qm[0]=max(max(ll.qm[0],rr.qm[0]),ll.rm[0]+rr.lm[0]);
return res;
}
if (hl) return ll;
return rr;
}
signed main()
{
n=read(),m=read();
for (int i = 1; i <= n; i++) a[i]=read();
bt(1,1,n);
while (m--)
{
int op=read();
if (op==0)
{
int l=read()+1,r=read()+1;
mod(1,l,r,0);
}
if (op==1)
{
int l=read()+1,r=read()+1;
mod(1,l,r,1);
}
if (op==2)
{
int l=read()+1,r=read()+1;
revers(1,l,r);
}
if (op==3)
{
int l=read()+1,r=read()+1;
writech(query1(1,l,r),'\n');
}
if (op==4)
{
int l=read()+1,r=read()+1;
writech(query2(1,l,r).qm[1],'\n');
}
}
return 0;
}
个人感觉可能是有标记冲突,但不会写qwq。