• 周六. 7 月 13th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

#线段树#洛谷 4428 [BJOI2018]二进制

admin

11 月 28, 2021

题目

有一个长为 (n) 的二进制串,支持单个位置取反,对于这个二进制串的一个子区间,
求出其有多少位置不同的连续子串,满足在重新排列后(可包含前导0)是一个 3 的倍数。


分析

考虑对于单个位置(2^imod 3)(1,2,1,2,cdots)
3的倍数有很多种情况,考虑补集转化,
设0的个数为(c0),1的个数为(c1),则不是3的倍数当且仅当

[egin{cases}c1=1&c0>1\c1 mod 2==1&c0leq 1end{cases}
]

由于支持单点修改,所以还需要一个线段树,
一个区间的答案等于左右区间的答案加上合并后多出的答案

一条一条考虑,上面这个只考虑(c1=1),再减掉(c0leq 1)的情况
单考虑(c1=1),即需要维护前后缀0的最长长度(l0,r0)
为了少判断,还需要维护(l1,r1)表示只有1个1的前后缀个数
那合并后多出的答案就是(lson.r1*rson.l0+lson.r0+rson.l1)
然后对于(c0=1)的情况当且仅当一个0和一个1相邻,那么合并的时候直接判断即可
对于(c0=0)的情况由于下一种情况被放到上面处理所以没有重复
对于(c1mod 2==1&c0leq 1)的情况,
(f[0/1][0/1])表示前缀或后缀0的个数为0或1且1的个数为偶数或奇数,直接转移即可


代码

#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
const int N=100011; typedef long long lll; int n,a[N];
struct rec{int lo,ro,co,cz,lz,rz,f[2][2],g[2][2]; lll w;}b[N<<2];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void print(lll ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
inline rec pup(rec t0,rec t1){
	rr rec t;
	t.lz=t0.lz+(t0.co?0:t1.lz),t.rz=t1.rz+(t1.co?0:t0.rz);
	t.co=t0.co+t1.co,t.cz=t0.cz+t1.cz;
	t.lo=t0.lo+(t0.co?(t0.co==1?t1.lz:0):t1.lo);
	t.ro=t1.ro+(t1.co?(t1.co==1?t0.rz:0):t0.ro);
	for (rr int i=0;i<2;++i)
	for (rr int j=0;j<2;++j){
		t.f[i][j]=t0.f[i][j]+(i>=t0.cz?t1.f[i-t0.cz][(j^t0.co)&1]:0);
		t.g[i][j]=t1.g[i][j]+(i>=t1.cz?t0.g[i-t1.cz][(j^t1.co)&1]:0);
	}
	t.w=t0.w+t1.w+1ll*t0.rz*t1.lo+1ll*t0.ro*t1.lz;
	for (rr int i0=0;i0<2;++i0)
	for (rr int i1=0;i1<2;++i1) if (i0+i1<2)
		t.w+=1ll*t0.g[i0][0]*t1.f[i1][1]+1ll*t0.g[i0][1]*t1.f[i1][0];
    if ((!t0.rz&&t1.lz)||(t0.rz&&!t1.lz)) --t.w;
	return t;
}
inline void pdown(rec &t,int x){
	memset(t.f,0,sizeof(t.f));
	memset(t.g,0,sizeof(t.g));
	if (x) t.lo=t.ro=t.co=t.w=1,t.cz=t.lz=t.rz=0,t.f[0][1]=t.g[0][1]=1;
	    else t.lo=t.ro=t.co=t.w=0,t.cz=t.lz=t.rz=1,t.f[1][0]=t.g[1][0]=1; 
}
inline void build(int k,int l,int r){
	if (l==r){pdown(b[k],a[l]); return;}
	rr int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	b[k]=pup(b[k<<1],b[k<<1|1]);
}
inline void update(int k,int l,int r,int x){
	if (l==r){pdown(b[k],a[l]); return;}
	rr int mid=(l+r)>>1;
	if (x<=mid) update(k<<1,l,mid,x);
	    else update(k<<1|1,mid+1,r,x);
    b[k]=pup(b[k<<1],b[k<<1|1]);
}
inline rec query(int k,int l,int r,int x,int y){
	if (l==x&&r==y) return b[k];
	rr int mid=(l+r)>>1;
	if (y<=mid) return query(k<<1,l,mid,x,y);
	else if (x>mid) return query(k<<1|1,mid+1,r,x,y);
	    else return pup(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y));
}
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i) a[i]=iut();
	build(1,1,n);
	for (rr int T=iut();T;--T){
		rr int opt=iut();
		if (opt==1){
			rr int x=iut();
			a[x]^=1,update(1,1,n,x);
		}else{
			rr int l=iut(),r=iut();
			rr rec t=query(1,1,n,l,r);
			rr lll ans=1ll*(r-l+1)*(r-l+2)>>1;
			print(ans-t.w),putchar(10);
		}
	}
	return 0;
}

发表回复