题解 P4428 【[BJOI2018]二进制】
yybyyb
·
·
题解
二进制串在模3意义下，每一位代表的余数显然是121212这样子交替出现的。
其实换种方法看，就是1,-1,1,-1,...
如果询问一个二进制串能否被3整除，那么只需要考虑奇数位上的1的个数和偶数位上的1的个数就行了。
如果可以重排，我们来考虑如何分配。
首先对于一个长度为len的区间，模3余1的位有[\frac{len+1}{2}]个，余-1的有[\frac{len}{2}]个。假设要分配k个1。
凑成3的倍数的情况一定是1,-1两两配对，剩下较多的那个的数量是3的倍数。
如果k是偶数那么一定可以两两配对。
如果k是奇数的话，就只能k-3个1均匀分配给-1,1，剩下3个分配给1。
那么需要满足\frac{k+3}{2}\le [\frac{len+1}{2}]，拆开后如果len是奇数则要满足k\le len-2，如果len是偶数则满足k\le len-3。
那么这个条件再进一步就是，如果0的个数\ge 3，那么一定满足。
如果0的个数为2，此时len=k+2 为奇数，也满足。
所以不合法的情况就是
- 只有一个1的区间(k\lt 3,且k为奇数就只有1)
- 出现了奇数个1，且0的个数为0/1。
因为要做到不重，所以第一个条件可以补充成“区间内只有1个1， 且0的个数不少于2个”。
答案就可以用总的连续子序列的个数减去不合法的数量。
可以用线段树维护不合法的连续子序列的数量。
考虑合并两个节点之后如何产生贡献，
设dl[0/1][0/1]表示强制选择左端点的一段连续区间中，0的出现次数为0/1，1的出现次数的奇偶性为0/1的序列个数，dr同理。
再统计一下左右连续的$0$的个数，以及区间内$0/1$的个数。
每次考虑跨过两段的不合法区间，统计答案即可。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 100100
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,Q,a[MAX];
struct data
{
ll dl[2][2],dr[2][2],fl[3],fr[3],l0,r0,s;
int s0,s1;
void init()
{
dl[0][0]=dr[0][0]=dl[0][1]=dr[0][1]=dl[1][0]=dr[1][0]=dl[1][1]=dr[1][1]=0;
fl[0]=fr[0]=fl[1]=fr[1]=fl[2]=fr[2]=0;
l0=r0=s0=s1=s=0;
}
data(){init();}
void pre(int x)
{
init();
if(x)dl[0][1]=dr[0][1]=s1=s=fl[0]=fr[0]=1;
else dl[1][0]=dr[1][0]=s0=l0=r0=1;
}
}t[MAX<<2];
data Merge(data A,data B)
{
data c;c.init();
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
{
c.dl[i][j]+=A.dl[i][j];
c.dr[i][j]+=B.dr[i][j];
if(i>=A.s0)c.dl[i][j]+=B.dl[i-A.s0][j^(A.s1&1)];
if(i>=B.s0)c.dr[i][j]+=A.dr[i-B.s0][j^(B.s1&1)];
}
for(int i=0;i<3;++i)
{
c.fl[i]+=A.fl[i];c.fr[i]+=B.fr[i];
if(!A.s1)c.fl[min(2,i+A.s0)]+=B.fl[i];
if(!B.s1)c.fr[min(2,i+B.s0)]+=A.fr[i];
}
if(A.s1==1&&B.l0)c.fl[min(2ll,A.s0+B.l0)]+=1,c.fl[2]+=B.l0-1;
if(B.s1==1&&A.r0)c.fr[min(2ll,B.s0+A.r0)]+=1,c.fr[2]+=A.r0-1;
c.l0=(A.s1==0)?A.l0+B.l0:A.l0;
c.r0=(B.s1==0)?B.r0+A.r0:B.r0;
c.s0=A.s0+B.s0;c.s1=A.s1+B.s1;
c.s=A.s+B.s;
c.s+=A.dr[0][0]*(B.dl[0][1]+B.dl[1][1]);
c.s+=A.dr[0][1]*(B.dl[0][0]+B.dl[1][0]);
c.s+=A.dr[1][0]*B.dl[0][1];
c.s+=A.dr[1][1]*B.dl[0][0];
if(B.l0)c.s+=B.l0*(A.fr[0]+A.fr[1]+A.fr[2])-A.fr[0];
if(A.r0)c.s+=A.r0*(B.fl[0]+B.fl[1]+B.fl[2])-B.fl[0];
return c;
}
void Build(int now,int l,int r)
{
if(l==r){t[now].pre(a[l]);return;}
int mid=(l+r)>>1;
Build(lson,l,mid);Build(rson,mid+1,r);
t[now]=Merge(t[lson],t[rson]);
}
void Modify(int now,int l,int r,int p)
{
if(l==r){t[now].pre(a[l]);return;}
int mid=(l+r)>>1;
if(p<=mid)Modify(lson,l,mid,p);
else Modify(rson,mid+1,r,p);
t[now]=Merge(t[lson],t[rson]);
}
data Query(int now,int l,int r,int L,int R)
{
if(L==l&&R==r)return t[now];
int mid=(l+r)>>1;
if(R<=mid)return Query(lson,l,mid,L,R);
if(L>mid)return Query(rson,mid+1,r,L,R);
return Merge(Query(lson,l,mid,L,mid),Query(rson,mid+1,r,mid+1,R));
}
int main()
{
n=read();
for(int i=1;i<=n;++i)a[i]=read();
Build(1,1,n);
Q=read();
while(Q--)
{
int opt=read(),l=read(),r;
if(opt==1)a[l]^=1,Modify(1,1,n,l);
else r=read(),printf("%lld\n",1ll*(r-l+1)*(r-l+2)/2-Query(1,1,n,l,r).s);
}
return 0;
}
```