【BZOJ5294】[BJOI2018]二进制（线段树）
题面
题解
二进制串在模(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)是奇数则要满足(kle len-2)，如果(len)是偶数则满足(kle len-3)。
那么这个条件再进一步就是，如果(0)的个数(ge 3)，那么一定满足。
如果(0)的个数为(2)，此时(len=k+2) 为奇数，也满足。
所以不合法的情况就是
- 只有一个(1)的区间((klt 3),且(k)为奇数就只有(1))
- 出现了奇数个(1)，且(0)的个数为(0/1)。
因为要做到不重，所以第一个条件可以补充成“区间内只有(1)个(1)，且(0)的个数不少于(2)个”。
答案就可以用总的连续子序列的个数减去不合法的数量。
可以用线段树维护不合法的连续子序列的数量。
考虑合并两个节点之后如何产生贡献，
设(dl[0/1][0/1])表示强制选择左端点的一段连续区间中，(0)的出现次数为(0/1)，(1)的出现次数的奇偶性为(0/1)的序列个数，(dr)同理。
(fl[0/1/2])表示强制经过左端点，(1)恰好出现了(1)次，且(0)的出现次数为(0,1,ge 2)的序列个数。(fr)同理。
再统计一下左右连续的(0)的个数，以及区间内(0/1)的个数。
每次考虑跨过两段的不合法区间，统计答案即可。
#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
",1ll*(r-l+1)*(r-l+2)/2-Query(1,1,n,l,r).s);
}
return 0;
}