自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 23:02:34，当前版本为作者最后更新于2024-08-24 20:10:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

抽象的官解，爽飞的四天。

发现两种操作都是整体的批量操作而没有针对单点的，所以感性理解一下这些操作是很不“自由”的，推理一下发现确实如此。

由于 D 操作针对元素而不是序列，所以下面直接认为序列是所有为 $1$ 位置构成的集合，$D(A)$ 表示对 $A$ 进行一次 D 操作后的集合。

首先，如果进行了一次 D 操作后，那么再次进行 D 操作不会改变，但如果取反（就是 B 操作，这么说直观一些，下同）后会发现只要它不是空集，那么它就拥有至少一半的元素（即值是 $1$）。那么猜想这个序列进行一次 D 操作后一定会变成全集，证明如下：

发现所有的情况都严格不劣于恰有 $2^{n-1}$ 个元素的情况，也就是操作前的集合（设它为 $A$）的线性基大小为 $n-1$。那么此时不妨设线性基中没有 $1$ （即最高位是 $2^0$）。那么取反后一定满足 $1$ 在集合里面，而 $\forall x \in (0,2^n-1)$ 一定有 $x \in A$ 或 $x \oplus 1 \in A$，因此如果再进行一次 D 操作就一定有 $x,x \oplus 1 \in D(A)$，因此可知 $D(A) = U$。

同样的，也可以得到 $A$ 和它的补集中至少有一个进行 D 变换后会变成全集。

那么有了这些结论，就不难发现可能的集合只有 $O(1)$ 种，经过梳理，发现有八种：

1. $A$ 及其补集（即 B 操作，下同）。
2. $D(A)$ 或 $D(U\setminus A)$ 及其补集。
3. $U$
4. $\emptyset$
5. $\{0\}$ 及其补集。

对于第五条的解释：$D(\emptyset) = \{0\}$。

因此只需要用一个数就能存储整个集合，并实现 $O(1)$ 单次变换和查询。

其实这里跟官解前面的那些观察差不多。

每次需要变换一个区间，这是容易维护的，线段树即可维护，记录每个节点的函数值以及每种数列的经过次数即可。总复杂度 $O(n2^n +8^2m + 8q\log m)$，把 $8$ 认为和 $\log m$ 同阶的话甚至刚好平衡了，不用上猫树。

可能复杂度有些高？官解最后靠循环节直接计算倒也是个思路，主要是利用了 BD 两个操作连续进行多次都没有意义，幸好没卡我的。但我觉得代码复杂度肯定是我优。

代码

#include<cstdio>
#define TY int
#define MAXN 262144
#define FOR(i,a,b) for(TY i=(a);i<=(b);i=-~i)
#define fOR(i,a,b) for(TY i=(a);i<(b);i=-~i)
#define ROF(i,a,b) for(TY i=(a);i>=(b);i=~-i)
#define rOF(i,a,b) for(TY i=(a);i>(b);i=~-i)
#define EDG(i,u) for(TY i=hed[u];i;i=nxt[i])
using namespace std;
typedef long long ll;
const TY M=998244353;
typedef unsigned long long ull;
TY _abs(TY a){return a<0?-a:a;}
TY maxn(TY a,TY b){return a>b?a:b;}
TY minn(TY a,TY b){return a<b?a:b;}
inline void updmx(TY &x,TY y){if(x<y)x=y;}
inline void updmn(TY &x,TY y){if(x>y)x=y;}
inline void add(TY &x,TY y){if((x+=y)>=M)x-=M;}
TY gcd(TY a,TY b){return b?gcd(b,a%b):a;}
TY qp(TY a,TY b){TY ans=1;do{if(1&b)ans=ans*a%M;a=a*a%M;}while(b>>=1);return ans;}
char getc(){char ch=getchar();while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();return ch;}
TY qr(){
	char ch=getchar();TY s=0,x=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')x=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';return x*s;
}void qw(TY a){if(a>9)qw(a/10);putchar(a%10+'0');}
void qw(TY a,char ch){
	if(a<0){a=-a;putchar('-');}
	if(a>9)qw(a/10);putchar(a%10+'0');
	if(ch)putchar(ch);
}TY n,m,T,b[MAXN],ct,kd,x,l,r,to[2][8],ar[18],nm,tot[MAXN][8],vl[8],ans;
TY tre[MAXN<<1][8],sm[MAXN<<1][8][8],tmp[8];
bool a[MAXN],t[MAXN];char s[MAXN];
//集合编号按题解中列举顺序，0代表B变换，1代表D变换
void ins(TY x){
	ROF(i,n-1,0)if((1<<i)&x){
		if(ar[i]){x^=a[i];continue;}
		ar[i]=x;++nm;return;
	}
}void dfs(TY x,TY v){
	if(x==n){t[v]=true;return;}
	dfs(x+1,v);if(ar[x])dfs(x+1,v^ar[x]);
}void build(TY i,TY j,TY id){
	if(i==j){
		if(s[i]=='B')fOR(i,0,8){
			tre[id][i]=to[0][i];
			sm[id][i][to[0][i]]=1;
		}else fOR(i,0,8){
			tre[id][i]=to[1][i];
			sm[id][i][to[1][i]]=1;
		}return;
	}TY mid=i+j>>1,sn=id<<1;
	build(i,mid,sn);build(mid+1,j,sn|1);
	fOR(i,0,8){
		tre[id][i]=tre[sn|1][tre[sn][i]];
		fOR(j,0,8)sm[id][i][j]=sm[sn][i][j]+sm[sn|1][tre[sn][i]][j];
	}
}void ask(TY i,TY j,TY id){
	if(l<=i&&j<=r){
		fOR(i,0,8)tmp[i]+=sm[id][x][i];
		x=tre[id][x];return;
	}TY mid=i+j>>1;
	if(l<=mid)ask(i,mid,id<<1);
	if(r>mid)ask(mid+1,j,id<<1|1);
}int main(){
	fOR(i,0,8)to[0][i]=i^1;
	to[1][2]=2;to[1][3]=4;
	to[1][4]=4;to[1][5]=6;
	to[1][6]=6;to[1][7]=4;
	n=qr();m=qr();T=qr();
	fOR(i,0,1<<n)a[i]=qr();scanf("%s",s+1);
	if(n==1){to[1][0]=0;to[1][1]=1;}//n=1需要特殊考虑
	else{
		fOR(i,0,1<<n)if(a[i])ins(i);
		if(nm==n)to[1][0]=4;
		else{dfs(0,0);to[1][0]=2;}
		fOR(i,nm=0,n)ar[i]=0;
		fOR(i,0,1<<n)if(!a[i])ins(i);
		if(nm==n)to[1][1]=4;
		else{dfs(0,0);to[1][1]=2;}
	}fOR(i,0,1<<n)if(a[i])++vl[0];vl[1]=(1<<n)-vl[0];
	fOR(i,0,1<<n)if(t[i])++vl[2];vl[3]=(1<<n)-vl[2];
	vl[4]=1<<n;vl[6]=1;vl[7]=(1<<n)-1;build(1,m,1);
	while(T--){
		kd=qr();
		if(kd==2){
			x=qr();l=qr();
			switch(b[x]){
				case 0:qw(a[l],'\n');break;
				case 1:qw(a[l]^1,'\n');break;
				case 2:qw(t[l],'\n');break;
				case 3:qw(t[l]^1,'\n');break;
				case 4:printf("1\n");break;
				case 5:printf("0\n");break;
				case 6:qw(!l,'\n');break;
				case 7:qw(!!l,'\n');break;
			}continue;
		}if(kd==1){
			x=qr();l=qr();r=qr();x=b[x];
			fOR(i,0,8)tmp[i]=0;ask(1,m,1);
			b[++ct]=x;qw(vl[b[ct]],'\n');
			fOR(i,0,8)tot[ct][i]=tmp[i];
		}else{
			x=qr();l=qr();ans=tot[x][4];
			if(a[l])ans+=tot[x][0];else ans+=tot[x][1];
			if(t[l])ans+=tot[x][2];else ans+=tot[x][3];
			if(l)ans+=tot[x][7];else ans+=tot[x][6];qw(ans,'\n');
		}
	}return 0;
}