写的 $\mathcal{O}(Tn)$，现在卡在 1.08s 卡不动了，要吐了。

#include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <random>
#include <cstring>
#include <ctime>
#include <cmath>
#include <assert.h> 
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define LL long long
#define pp pair<LL,int>
#define mp make_pair 
#define ull unsigned long long
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
	//	return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
		return getchar();
	}
	template<class T> void gi(T& x){
		x=0; int f=1;char c=gc();
		if(c=='-')f=-1;
		for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
		x=x*f;
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void pi(T x,char c='\n'){
		if(x<0)pc('-'),x=-x;
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
using IO::pc;
const int mod=1e9+7;
inline int add(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
inline int dec(int x,int y){
	return x-y<0?x-y+mod:x-y;
}
inline int mul(int x,int y){
	return 1ll*x*y%mod;
}
inline int qkpow(int a,int b){
	if(b<0)return 0;
	int ans=1,base=a%mod;
	while(b){
		if(b&1)ans=1ll*ans*base%mod;
		base=1ll*base*base%mod;
		b>>=1;
	}
	return ans;
}
int fac[2000005],inv[2000005],Invn[600005];
inline int binom(int n,int m){
	if(n<m||m<0)return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void init_C(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod; 
	inv[0]=1;
	inv[n]=qkpow(fac[n],mod-2);
	for(int i=n-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
//	Invn[0]=Invn[1]=1;
//	for(int i=1;i<=200000;i++)Invn[i]=(LL)(mod-mod/i)*Invn[mod%i]%mod;
}
int T,n,m,K,rt,ta[200005],c[200005],a[200005],X[5],h[300005],f[300005],g[300005],mi[300005],lim,nt,rev[300005];
bool rule[300005];
LL res,sum[300005];
#define ls(x) x<<1
#define rs(x) x<<1|1
inline void dfs(int x,int t){
	f[x]=-1,g[x]=t+1;
	if(x>=(1<<K))return ;
	h[ls(x)]=h[rs(x)]=h[x]-1;
	int y=(x<<1)+rule[x];
	if(mi[x])mi[ls(x)]=mi[rs(x)]=mi[x];
	else mi[y]=h[x],mi[y^1]=0;
	dfs(ls(x),t),dfs(rs(x),t);
}
inline void updata(int x,int ti){
	for(;x>=rt&&f[x]==-1;x>>=1){
		int y=(x<<1)+rule[x];
		if(f[y]==-1){
			f[x]=f[y];
			break;
		}
		else if(f[y]>=h[x]){
			f[x]=f[y];
			if(g[y^1]==nt)g[y^1]=ti;
		}
		else {
			if(f[y^1]==-1)break;
			f[x]=f[y^1];
		}
	}
}
inline void dfs2(int x,int mi){
	mi=min(mi,g[x]);
	if(mi<=lim)return ;
	if(x>=(1<<K)){
		sum[min(n,mi-1)]+=x-(1<<K)+1;
		return ;
	}
	dfs2(ls(x),mi),dfs2(rs(x),mi);
}
inline void solve2(int t){
	if(t==0){
		if(rev[1])res^=rev[1];
		return ;
	}
	rt=1<<(K-t);nt=(1<<t)+1;
	h[rt]=t,mi[rt]=0;
	dfs(rt,1<<t);
	int up=min((1<<t),n);
	for(int i=1;i<=up;i++){
		int id=i+(1<<K)-1;
		if(a[i]<mi[id])g[id]=min(g[id],i);
		f[id]=a[i];
		updata(id>>1,i);
		sum[i]=0;
	}
	lim=(1<<t-1)+1;
	dfs2(rt,g[rt]);
	if(rev[up])res^=(sum[up]*rev[up]);
	for(int i=up-1;i>=(1<<(t-1))+1;i--){
		sum[i]+=sum[i+1];
		if(rev[i])res^=(sum[i]*rev[i]);
	}
}
inline void solve(){
	for(int i=0;i<=3;i++)gi(X[i]);
	for(int i=1;i<=n;i++)a[i]=ta[i]^X[i&3];
	res=0;
	for(int i=K;i>=0;i--)solve2(i);
	pi(res);
}
char s[200005];
signed main(){
//	freopen("arena.in","r",stdin);
	srand(time(0));
	gi(n),gi(m);
	for(int i=1;i<=n;i++)gi(ta[i]);
	for(int i=1;i<=m;i++)gi(c[i]),rev[c[i]]=i;
	while((1<<K)<n)K++;
	for(int i=K-1;i>=0;i--){
		scanf("%s",s);
		for(int j=0;j<(1<<i);j++){
			rule[(1<<i)+j]=s[j]-'0';
		}
	}
	gi(T);
	while(T--)solve();
	return 0;
} 
/*
*/