2019.02.12 bzoj5294: [Bjoi2018]二进制（线段树）

时间：2022-03-17 08:41:33

传送门

题意简述：

给出一个长度为nnn的二进制串。

你需要支持如下操作：

  1. 修改每个位置：1变0,0变1
  2. 询问对于一个区间的子二进制串有多少满足重排之后转回十进制值为333的倍数（允许前导000）。

思路：

考虑一个xxx位的包含有yyy个111的二进制串，它是333的倍数当如下任意一个条件成立：

  1. yyy是偶数。
  2. yyy是大于111的奇数且x−y>=2x-y>=2x−y>=2

emmmmemmmmemmmm感觉不是很好维护。

于是我们正难则反，跑去求不合法的方案数，这个二进制串不合法如下任意一个条件成立：

  1. yyy是奇数大于111且x−y&lt;2x-y&lt;2x−y<2
  2. y=1y=1y=1

这个答案可以用线段树维护了（其实上面的也可以只是感觉不太好写）。

我们定义两类状态：

  • C0/1,0/1,0/1,0/1C_{0/1,0/1,0/1,0/1}C0/1,0/1,0/1,0/1​表示从区间左/右端点开始的连续一段二进制串，满足其中有偶/奇数个111，串中111的个数不大于/大于111个，串中有0/10/10/1个000的这样的二进制串个数。
  • D0/1,0/1D_{0/1,0/1}D0/1,0/1​表示从区间左/右端点开始的连续一段二进制串，满足其中有0/10/10/1个111的这样的二进制串的个数。

然后分类转移一下即可。

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5;
typedef long long ll;
int n;
bool a[N];
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
inline int add(const ll&a,const ll&b){return !a*b?0:a+b;}
namespace SGT{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define mid (T[p].l+T[p].r>>1)
	struct Node{int l,r,det;ll ans,c[2][2][2][2],d[2][2];}T[N<<2];
	inline Node operator+(const Node&a,const Node&b){
		Node ret;
		ret.l=a.l,ret.r=b.r,ret.det=a.det+b.det,ret.ans=a.ans+b.ans,memset(ret.c,0,sizeof(ret.c));
		ret.d[0][0]=a.d[0][0]+(a.det?0:b.d[0][0]);
		ret.d[0][1]=a.d[0][1]+(a.det<2?b.d[0][1-a.det]:0);
		ret.d[1][0]=b.d[1][0]+(b.det?0:a.d[1][0]);
		ret.d[1][1]=b.d[1][1]+(b.det<2?a.d[1][1-b.det]:0);
		for(ri i=0;i<2;++i)for(ri j=0;j<2;++j)for(ri k=0;k<2;++k)ret.c[0][i][j][k]=a.c[0][i][j][k],ret.c[1][i][j][k]=b.c[1][i][j][k];
		int tl=a.r-a.l+1-a.det,tr=b.r-b.l+1-b.det;
		for(ri k=0;k+tl<2;++k){
			ret.c[0][0][0][k+tl]+=a.det?0:b.c[0][0][0][k];
			ret.c[0][0][1][k+tl]+=b.c[0][a.det&1][1][k]+(a.det?b.c[0][a.det&1][0][k]:0);
			ret.c[0][1][0][k+tl]+=a.det<2?b.c[0][1-a.det][0][k]:0;
			ret.c[0][1][1][k+tl]+=b.c[0][(a.det&1)^1][1][k]+(a.det>1?b.c[0][(a.det&1)^1][0][k]:0);
		}
		for(ri k=0;k+tr<2;++k){
			ret.c[1][0][0][k+tr]+=b.det?0:a.c[1][0][0][k];
			ret.c[1][0][1][k+tr]+=a.c[1][b.det&1][1][k]+(b.det?a.c[1][b.det&1][0][k]:0);
			ret.c[1][1][0][k+tr]+=b.det<2?a.c[1][1-b.det][0][k]:0;
			ret.c[1][1][1][k+tr]+=a.c[1][(b.det&1)^1][1][k]+(b.det>1?a.c[1][(b.det&1)^1][0][k]:0);
		}
		for(ri i=0;i<2;++i)for(ri j=0;i+j<2;++j){
			ret.ans+=a.c[1][0][0][i]*b.c[0][1][1][j]+a.c[1][0][1][i]*b.c[0][1][1][j]+a.c[1][0][1][i]*b.c[0][1][0][j];
            ret.ans+=a.c[1][1][0][i]*b.c[0][0][1][j]+a.c[1][1][1][i]*b.c[0][0][1][j]+a.c[1][1][1][i]*b.c[0][0][0][j];
        }
		ret.ans+=a.d[1][0]*b.d[0][1]+a.d[1][1]*b.d[0][0];
		return ret;
	}
	inline void solve(int p){
		T[p].ans=T[p].det=0,memset(T[p].c,0,sizeof(T[p].c)),memset(T[p].d,0,sizeof(T[p].d));
		if(a[T[p].l])T[p].ans=T[p].det=T[p].c[0][1][0][0]=T[p].c[1][1][0][0]=T[p].d[0][1]=T[p].d[1][1]=1;
		else T[p].c[0][0][0][1]=T[p].c[1][0][0][1]=T[p].d[0][0]=T[p].d[1][0]=1;
	}
	inline void build(int p,int l,int r){
		T[p].l=l,T[p].r=r;
		if(l==r)return solve(p);
		build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc];
	}
	inline void update(int p,int k){
		if(T[p].l==T[p].r)return solve(p);
		update(k<=mid?lc:rc,k),T[p]=T[lc]+T[rc];
	}
	inline Node query(int p,int ql,int qr){
		if(ql<=T[p].l&&T[p].r<=qr)return T[p];
		if(qr<=mid)return query(lc,ql,qr);
		if(ql>mid)return query(rc,ql,qr);
		return query(lc,ql,mid)+query(rc,mid+1,qr);
	}
}
int main(){
	n=read();
	for(ri i=1;i<=n;++i)a[i]=read();
	SGT::build(1,1,n);
	for(ri tt=read(),op,l,r;tt;--tt){
		op=read();
		if(op==1)a[l=read()]^=1,SGT::update(1,l);
		else l=read(),r=read(),cout<<(ll)(r-l+1)*(r-l+2)/2-SGT::query(1,l,r).ans<<'\n';
	}
	return 0;
}

相关文章