Iowa_BattleShip @ 2018-03-13 21:28:32
#include<cstdio>
using namespace std;
const int N=1e5+10;
struct co{
int x,y,s;
co()
{
x=s=y=0;
}
};
co o_1[N<<2],o_0[N<<2],o;
int a[N],s[N<<2],ch[N<<2];
bool xo[N<<2];
int re()
{
int x=0;
char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=x*10+(c-'0');
return x;
}
void pp(int r)
{
int lx=r<<1,ly=r<<1|1;
s[r]=s[lx]+s[ly];
if(o_1[lx].y==o_1[ly].x-1)
{
o_1[r].s=o_1[lx].s+o_1[ly].s;
o_1[r].x=o_1[lx].x;
o_1[r].y=o_1[ly].y;
}
else
if(o_1[lx].s>o_1[ly].s)
o_1[r]=o_1[lx];
else
o_1[r]=o_1[ly];
if(o_0[lx].y==o_0[ly].x-1)
{
o_0[r].s=o_0[lx].s+o_0[ly].s;
o_0[r].x=o_0[lx].x;
o_0[r].y=o_0[ly].y;
}
else
if(o_0[lx].s>o_0[ly].s)
o_0[r]=o_0[lx];
else
o_0[r]=o_0[ly];
}
void pn(int r,int x,int y)
{
int mid=(x+y)>>1,lx=r<<1,ly=r<<1|1,sl=mid-x+1,sr=y-mid,k=ch[r];
if(k)
{
ch[lx]=ch[ly]=k;
xo[lx]=xo[ly]=0;
if(k==1)
{
s[lx]=sl;
s[ly]=sr;
o_1[lx].s=sl;
o_1[lx].x=x;
o_1[lx].y=mid;
o_1[ly].s=sr;
o_1[ly].x=mid+1;
o_1[ly].y=y;
o_0[lx].s=o_0[lx].x=o_0[lx].y=0;
o_0[ly].s=o_0[ly].x=o_0[ly].y=0;
}
else
{
s[lx]=s[ly]=0;
o_0[lx].s=sl;
o_0[lx].x=x;
o_0[lx].y=mid;
o_0[ly].s=sr;
o_0[ly].x=mid+1;
o_0[ly].y=y;
o_1[lx].s=o_1[lx].x=o_1[lx].y=0;
o_1[ly].s=o_1[ly].x=o_1[ly].y=0;
}
ch[r]=0;
return;
}
if(xo[r])
{
xo[lx]^=1;
xo[ly]^=1;
s[lx]=sl-s[lx];
s[ly]=sr-s[ly];
o=o_1[lx];
o_1[lx]=o_0[lx];
o_0[lx]=o;
o=o_1[ly];
o_1[ly]=o_0[ly];
o_0[ly]=o;
xo[r]=0;
}
}
void bu(int r,int x,int y)
{
int mid=(x+y)>>1;
if(x==y)
{
s[r]=a[x];
if(a[x])
{
o_1[r].s=1;
o_1[r].x=o_1[r].y=x;
}
else
{
o_0[r].s=1;
o_0[r].x=o_0[r].y=x;
}
return;
}
bu(r<<1,x,mid);
bu(r<<1|1,mid+1,y);
pp(r);
}
void fi(int r,int x,int y,int ql,int qr,int v)
{
int mid=(x+y)>>1;
if(ql<=x&&y<=qr)
{
if(!v)
{
ch[r]=-1;
xo[r]=0;
s[r]=0;
o_0[r].s=y-x+1;
o_0[r].x=x;
o_0[r].y=y;
o_1[r].s=o_1[r].x=o_1[r].y=0;
}
else
if(v==1)
{
ch[r]=1;
xo[r]=0;
s[r]=y-x+1;
o_1[r].s=y-x+1;
o_1[r].x=x;
o_1[r].y=y;
o_0[r].s=o_0[r].x=o_0[r].y=0;
}
else
{
xo[r]^=1;
s[r]=y-x+1-s[r];
o=o_1[r];
o_1[r]=o_0[r];
o_0[r]=o;
}
pn(r,x,y);
return;
}
pn(r,x,y);
if(ql<=mid)
fi(r<<1,x,mid,ql,qr,v);
if(mid<qr)
fi(r<<1|1,mid+1,y,ql,qr,v);
pp(r);
}
int qu_s(int r,int x,int y,int ql,int qr)
{
int mid=(x+y)>>1,k=0;
if(ql<=x&&y<=qr)
return s[r];
pn(r,x,y);
if(ql<=mid)
k+=qu_s(r<<1,x,mid,ql,qr);
if(mid<qr)
k+=qu_s(r<<1|1,mid+1,y,ql,qr);
return k;
}
co qu_o(int r,int x,int y,int ql,int qr)
{
int mid=(x+y)>>1;
bool p=0;
co k,kk;
if(ql<=x&&y<=qr)
return o_1[r];
pn(r,x,y);
if(ql<=mid)
{
k=qu_o(r<<1,x,mid,ql,qr);
p=1;
}
if(mid<qr)
{
kk=qu_o(r<<1|1,mid+1,y,ql,qr);
if(k.y==kk.x-1)
{
k.s+=kk.s;
k.y=kk.y;
}
else
if(k.s<kk.s)
k=kk;
}
return p?k:kk;
}
int main()
{
int i,n,m,x,y,p;
n=re();
m=re();
for(i=1;i<=n;i++)
a[i]=re();
bu(1,1,n);
while(m--)
{
p=re();
x=re();
y=re();
x++;
y++;
if(p>=0&&p<3)
fi(1,1,n,x,y,p);
else
if(p==3)
printf("%d\n",qu_s(1,1,n,x,y));
else
printf("%d\n",qu_o(1,1,n,x,y).s);
}
return 0;
}
by 夏色祭 @ 2018-03-13 21:54:02
您可以写个对拍啊
by Iowa_BattleShip @ 2018-03-14 09:06:36
@zykykyk 对拍拍了,但是调试调不出什么毛病,目前知道是取反的标记有问题,但看了半小时找不到哪里有问题……
by Iowa_BattleShip @ 2018-03-14 12:32:32
已AC,谢谢