答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
template<class T>void rd(T &x) {
static char ch(0);
for(x=0,ch=getc(); !isdigit(ch); ch=getc());
for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
}
template<class T>void wr(T x,const char End='\n') {
static int top(0);
static int st[50];
do st[++top]=x%10,x/=10;
while(x);
while(top)putc(st[top]^'0'),--top;
putc(End);
}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
if(L>R)return;
if(!h) {
int x(u-(1<<k)+1);
if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
return;
}
dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
rd(n),rd(m);
while((1<<k)<n)++k;
FOR(i,1,n)rd(a_[i]);
FOR(i,1,m)rd(c[i]);
DOR(i,k-1,0) {
scanf("%s",s);
DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
}
rd(Q);
while(Q--) {
static int X[4];
rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
FOR(i,1,n)a[i]=a_[i]^X[i&3];
dfs0(1,k),RCL(sum+1,0,ll,n);
FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
FOR(i,1,n)sum[i]+=sum[i-1];
ll ans(0);
FOR(i,1,m)ans^=i*sum[c[i]];
wr(ans);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
template<class T>void rd(T &x) {
static char ch(0);
for(x=0,ch=getc(); !isdigit(ch); ch=getc());
for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
}
template<class T>void wr(T x,const char End='\n') {
static int top(0);
static int st[50];
do st[++top]=x%10,x/=10;
while(x);
while(top)putc(st[top]^'0'),--top;
putc(End);
}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
if(L>R)return;
if(!h) {
int x(u-(1<<k)+1);
if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
return;
}
dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
rd(n),rd(m);
while((1<<k)<n)++k;
FOR(i,1,n)rd(a_[i]);
FOR(i,1,m)rd(c[i]);
DOR(i,k-1,0) {
scanf("%s",s);
DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
}
rd(Q);
while(Q--) {
static int X[4];
rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
FOR(i,1,n)a[i]=a_[i]^X[i&3];
dfs0(1,k),RCL(sum+1,0,ll,n);
FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
FOR(i,1,n)sum[i]+=sum[i-1];
ll ans(0);
FOR(i,1,m)ans^=i*sum[c[i]];
wr(ans);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls x<<1
#define rs x<<1|1
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define ll long long
using namespace std;
const int N = (1 << 17) + 5;
int mx[20][N << 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1;
bool vis[N];
ll ans[N], sum;
struct node {
ll sum;
int x;
bool tp, d;
} t[N << 2];
inline void build(int x, int l, int r) {
if (l == r) {
t[x].x = l;
return ;
}
int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
build(lson);
build(rson);
int win = a[t[x << 1 | d].x] >= k;
t[x].x = t[x << 1 | (d ^ !win)].x;
if (!d && win)t[x].tp = 1, ok[r]++, ok[mid]--;
else t[x].tp = 0;
}
inline void build2(int x, int l, int r, int *mx) {
t[x].sum = (l + r) * (r - l + 1ll) / 2;
if (l == r)return ;
int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
if (~mx[x])mx[ls] = mx[rs] = mx[x];
else mx[x << 1 | d] = k;
build2(lson, mx);
build2(rson, mx);
}
inline void up(int x) {
sum += !vis[x] * x;
vis[x] = 1;
}
inline int rd() {
char c;
int f = 1;
while (!isdigit(c = getchar()))if (c == '-')f = -1;
int x = c - '0';
while (isdigit(c = getchar()))x = x * 10 + (c ^ 48);
return x * f;
}
inline char gc() {
char c;
while ((c = getchar()) <= ' ');
return c;
}
int main() {
// freopen("arena.in","r",stdin);
// freopen("arena.out","w",stdout);
n = rd();
m = rd();
for (int i = 1; i <= n; i++)aa[i] = rd();
for (int i = 1; i <= m; i++)c[i] = rd();
while (nn < n)nn <<= 1;
for (int i = 2; i <= nn; i++)lg[i] = lg[i >> 1] + 1;
for (int i = nn / 2; i; i >>= 1)
for (int j = i; j < i * 2; j++)
t[j].d = gc() - '0';
memset(mx, -1, sizeof mx);
for (int s = 0; (1 << s) <= nn; s++)
build2(1 << s, 1, nn>>s, mx[s]);
for (int T = rd(); T--;) {
int yh[4] = {rd(), rd(), rd(), rd()};
for (int i = 1; i <= n; i++)a[i] = aa[i] ^ yh[i & 3];
memset(ok, 0, sizeof ok);
build(1, 1, nn);
for (int i = nn, rt = 1, s = 0; i; i--) {
if ((1 << lg[i]) == i) {
if (i != nn)rt <<= 1, s++;
for (int j = 1; j <= i; j++)vis[j] = 0;
sum = 0;
up(t[rt].x);
}
ans[i] = sum;
if (ok[i] += ok[i + 1])continue;
up(i);
int x = i + nn - 1;
while (x != rt) {
int d = x & 1;
x >>= 1;
if (!d)
if (t[x].tp)sum += t[rs].sum;
else break;
else if (a[t[ls].x] >= mx[s][ls])up(t[ls].x);
}
}
ll num = 0;
for (int i = 1; i <= m; i++)num ^= i * ans[c[i]];
printf("%lld\n", num);
}
return 0;
}</pre>
这道题暂未补解析。