CreeperLordVader @ 2019-03-09 19:16:21
问题很奇怪
为什么加了调试语句以后答案就成了对的
不加就是错的??
数据:
20 6
1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1
1 7 11
2 4 19
2 12 13
4 16 18
0 9 9
3 5 10
最后一个询问应输出0,我输出2
但是对操作1加上调试语句后答案就又变成了0
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,m,a[MAXN];
int setc[MAXN<<2],rmax[MAXN<<2][2];
int rev[MAXN<<2],lmax[MAXN<<2][2];
int sub[MAXN<<2][2],sum[MAXN<<2];
void read(int& x)
{
char c=getchar();
x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void update(int o,int l,int r)
{
int mid=(l+r)>>1;
if(sum[o<<1]==mid-l+1)
{
lmax[o][1]=sum[o<<1]+lmax[o<<1|1][1];
lmax[o][0]=0;
}
else lmax[o][1]=lmax[o<<1][1];
if(!sum[o<<1])
{
lmax[o][0]=mid-l+1+lmax[o<<1|1][0];
lmax[o][1]=0;
}
else lmax[o][0]=lmax[o<<1][0];
if(sum[o<<1|1]==r-mid)
{
rmax[o][1]=sum[o<<1|1]+rmax[o<<1][1];
rmax[o][0]=0;
}
else rmax[o][1]=rmax[o<<1|1][1];
if(!sum[o<<1|1])
{
rmax[o][0]=r-mid+rmax[o<<1][0];
rmax[o][1]=0;
}
else rmax[o][0]=rmax[o<<1|1][0];
sub[o][1]=max(max(sub[o<<1][1],sub[o<<1|1][1]),rmax[o<<1][1]+lmax[o<<1|1][1]);
sub[o][0]=max(max(sub[o<<1][0],sub[o<<1|1][0]),rmax[o<<1][0]+lmax[o<<1|1][0]);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
void pushdown(int o,int l,int r)
{
int mid=(l+r)>>1;
if(setc[o]>=0)
{
rev[o]=rev[o<<1]=rev[o<<1|1]=0;
setc[o<<1]=setc[o];
setc[o<<1|1]=setc[o];
if(setc[o])
{
sub[o<<1][0]=lmax[o<<1][0]=rmax[o<<1][0]=0;
sum[o<<1]=lmax[o<<1][1]=rmax[o<<1][1]=sub[o<<1][1]=mid-l+1;
sub[o<<1|1][0]=lmax[o<<1|1][0]=rmax[o<<1|1][0]=0;
sum[o<<1|1]=lmax[o<<1|1][1]=rmax[o<<1|1][1]=sub[o<<1|1][1]=r-mid;
}
else
{
sub[o<<1][1]=lmax[o<<1][1]=rmax[o<<1][1]=0;
sum[o<<1]=0;
lmax[o<<1][0]=rmax[o<<1][0]=sub[o<<1][0]=mid-l+1;
lmax[o<<1][1]=rmax[o<<1][1]=sub[o<<1][1]=0;
sub[o<<1|1][1]=lmax[o<<1|1][1]=rmax[o<<1|1][1]=0;
sum[o<<1|1]=0;
lmax[o<<1|1][0]=rmax[o<<1|1][0]=sub[o<<1|1][0]=r-mid;
lmax[o<<1|1][1]=rmax[o<<1|1][1]=sub[o<<1|1][1]=0;
}
setc[o]=-1;
}
if(rev[o])
{
rev[o<<1]^=1;
rev[o<<1|1]^=1;
sum[o<<1]=mid-l+1-sum[o<<1];
sum[o<<1|1]=r-mid-sum[o<<1|1];
swap(sub[o<<1][0],sub[o<<1][1]);
swap(sub[o<<1|1][0],sub[o<<1|1][1]);
swap(lmax[o<<1][0],lmax[o<<1][1]);
swap(rmax[o<<1][0],rmax[o<<1][1]);
swap(lmax[o<<1|1][0],lmax[o<<1|1][1]);
swap(rmax[o<<1|1][0],rmax[o<<1|1][1]);
rev[o]=0;
}
}
void build(int o,int l,int r)
{
if(l==r)
{
sum[o]=a[l];
if(a[l])sub[o][1]=lmax[o][1]=rmax[o][1]=1;
else sub[o][0]=lmax[o][0]=rmax[o][0]=1;
return ;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
update(o,l,r);
}
void change(int o,int l,int r,int ql,int qr,int k)
{
if(ql<=l&&qr>=r)
{
if(k)
{
sub[o][1]=lmax[o][1]=rmax[o][1]=r-l+1;
sub[o][0]=lmax[o][0]=rmax[o][0]=0;
}
else
{
sub[o][0]=lmax[o][0]=rmax[o][0]=r-l+1;
sub[o][1]=lmax[o][1]=rmax[o][1]=0;
}
sum[o]=(r-l+1)*k;
setc[o]=k;
rev[o]=0;
return ;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid)change(o<<1,l,mid,ql,qr,k);
if(qr>mid)change(o<<1|1,mid+1,r,ql,qr,k);
update(o,l,r);
}
void flip(int o,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r)
{
sum[o]=r-l+1-sum[o];
swap(lmax[o][0],lmax[o][1]);
swap(rmax[o][0],rmax[o][1]);
swap(sub[o][0],sub[o][1]);
rev[o]^=1;
return ;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid)flip(o<<1,l,mid,ql,qr);
if(qr>mid)flip(o<<1|1,mid+1,r,ql,qr);
update(o,l,r);
}
int qsum(int o,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r)
{
return sum[o];
}
int mid=(l+r)>>1,ans=0;
pushdown(o,l,r);
if(ql<=mid)ans+=qsum(o<<1,l,mid,ql,qr);
if(qr>mid)ans+=qsum(o<<1|1,mid+1,r,ql,qr);
return ans;
}
int query(int o,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r)
{
return sub[o][1];
}
int mid=(l+r)>>1,ansl=-1,ansr=-1,lans=-1,rans=-1;
pushdown(o,l,r);
if(ql<=mid)
{
ansl=query(o<<1,l,mid,ql,qr);
if(qr>mid)lans=min(rmax[o<<1][1],mid-ql+1);
}
if(qr>mid)
{
ansr=query(o<<1|1,mid+1,r,ql,qr);
if(ql<=mid)rans=min(lmax[o<<1|1][1],qr-mid);
}
return max(max(ansl,ansr),lans+rans);
}
void debug()
{
for(int i=1;i<=n;i++)
cout<<qsum(1,1,n,i,i)<<" ";
cout<<endl;
}
int main()
{
read(n);
read(m);
for(int i=1;i<=n;i++)
{
read(a[i]);
}
build(1,1,n);
memset(setc,-1,sizeof(setc));
for(int i=1;i<=m;i++)
{
int op,l,r;
read(op);
read(l);
read(r);
l++;
r++;
switch(op)
{
case 0:
{
change(1,1,n,l,r,0);
// debug();
break;
}
case 1:
{
change(1,1,n,l,r,1);
// debug();
break;
}
case 2:
{
flip(1,1,n,l,r);
// debug();
break;
}
case 3:
{
// debug();
printf("%d\n",qsum(1,1,n,l,r));
break;
}
case 4:
{
printf("%d\n",query(1,1,n,l,r));
break;
}
}
}
}
/*
20 6
1 0 1 0 1 1 1 0 1 …
by hsfzLZH1 @ 2019-03-09 20:10:34
@CreeperLordVader 您没有及时 pushdown
吧
by CreeperLordVader @ 2019-03-09 20:14:36
@hsfzLZH1
我也怀疑是这样
但我看了每个地方都有PUSHDOWN啊
by hsfzLZH1 @ 2019-03-09 20:17:10
@CreeperLordVader 那您有没有都写 update
呢?
by CreeperLordVader @ 2019-03-09 20:21:31
@hsfzLZH1
修改都写了,查询函数没写,但那个也没必要
而且都写UPDATE以后结果一样