如果你的时间复杂度正确，并且只超时大概几十毫秒的样子。

在第二次dfs中加一个剪枝，判断当前的左边界是否大于可以更新的区间的右端点，如果更大则说明无法更新了。 详见下面代码注释的那一行。

#include<iostream>
#define ls(u) (u<<1)
#define rs(u) (u<<1|1)
using namespace std;
const int K=3e5+5,L=20;
const int inf=0x3f3f3f3f;
const int N=1e5+5,M=2e5+5;
bool op[K];
char s[L][N];
int f[K],g[K],p[L];
long long ans,sum[N];
int i,u,d,n,m,t,k,len;
int a[M],b[N],c[N],x[4];
inline void update(int l,int r,int v){
	if(l>r) return;
	sum[l]+=v,sum[r+1]-=v;
}void pre(int u,int d){
	p[d]++;
	if(d==k){
		f[u]=p[d];
		g[u]=min(n,f[u]-1);
		return;
	}op[u]=s[d][p[d]]-'0';
	pre(ls(u),d+1);
	pre(rs(u),d+1);
}void dfs1(int u,int d){
	if(d==k) return;
	dfs1(ls(u),d+1);
	dfs1(rs(u),d+1);
	if(op[u]){
		g[u]=g[rs(u)];
		if(a[f[rs(u)]]<k-d){
			f[u]=f[ls(u)];
			g[u]=max(g[u],g[ls(u)]);
		}else f[u]=f[rs(u)];
	}else{
		g[u]=g[ls(u)];
		if(a[f[ls(u)]]<k-d){
			f[u]=f[rs(u)];
			g[u]=max(g[u],g[rs(u)]);
		}else f[u]=f[ls(u)];
	}
}void dfs2(int u,int d,int l,int r,int x,int y){
	if(l>y) return; //如果算出来可更新区间的左边界比当前可更新右端点的值更大，则可以终止递归
	if(d==k){
		int p=f[u];
		if(a[p]>=x)
			update(max(l,p),min(r,y),p);
		update(l,min(p-1,y),p);
		return;
	}if(op[u]){
		dfs2(ls(u),d+1,l,r,x,a[f[rs(u)]]<k-d?y:min(y,g[rs(u)]));
		dfs2(rs(u),d+1,l,r,x?x:k-d,y);
	}else{
		dfs2(ls(u),d+1,l,r,x?x:k-d,y);
		dfs2(rs(u),d+1,l,r,x,a[f[ls(u)]]<k-d?y:min(y,g[ls(u)]));
	}
}int main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(i=1;i<=n;i++) cin>>b[i];
	for(i=1;i<=m;i++) cin>>c[i];
	while(1<<k<n) k++;
	for(i=k-1;~i;i--) cin>>s[i]+1;
	cin>>t,len=1<<k,pre(1,0);
	while(t--){
		for(i=0;i<4;i++) cin>>x[i];
		for(i=1;i<=n;i++) sum[i]=0ll;
		for(i=n+1;i<=len;i++) a[i]=inf;
		for(i=1;i<=n;i++) a[i]=b[i]^x[i%4];
		u=1,d=0,dfs1(1,0),update(1,1,1);
		for(;d<k;u<<=1,d++)
			dfs2(u,d,(1<<k-d-1)+1,1<<k-d,0,n);
		for(i=2;i<=n;i++) sum[i]+=sum[i-1];
		for(ans=0ll,i=1;i<=m;i++) ans^=sum[c[i]]*i;
		cout<<ans<<'\n';
	}return 0;
}