题解

#include <bits/stdc++.h>
using LL = long long;
const int N = 1 << 18 | 7;
const int M = 18;
int n, m, t, aa[N], a[N], c[N];
int b[N], r[N], id[N], lp[N], rp[N];
LL sum[N], ans[N];
char s[M][N];
void build() {
for(int i = 0; i < t; ++i) {
r[i + t] = 0;
id[i + t] = i;
b[i + t] = i + 1;
sum[i + t] = lp[i + t] = rp[i + t] = i + 1;
}
for(int i = t - 1; i >= 1; --i) {
r[i] = r[i << 1] + 1;
id[i] = id[i << 1] >> 1;
lp[i] = lp[i << 1];
rp[i] = rp[i << 1 | 1];
sum[i] = sum[i << 1] + sum[i << 1 | 1];
if(s[r[i]][id[i]] == '0')
b[i] = a[b[i << 1]] >= r[i] ? b[i << 1] : b[i << 1 | 1];
else
b[i] = a[b[i << 1 | 1]] >= r[i] ? b[i << 1 | 1] : b[i << 1];
}
}
LL vt[N], st;
int rd;
void dfs(int i, LL ss, int zl) {
if(i >= t) {
ans[i - t] = st + ss + lp[i];
return ;
}
LL trd = rd, tst = st;
if(s[r[i]][id[i]] == '0') {
if(b[i] == b[i << 1]) {
LL v = a[b[i]] >= rd ? b[i] : a[b[i]] + 1 >= zl ? 0 : vt[a[b[i]] + 1];
stdfill(ans + lp[i << 1 | 1] - 1, ans + rp[i << 1 | 1], v + ss);
}
else {
vt[r[i]] = vt[r[i] + 1];
dfs(i << 1 | 1, ss, zl);
}
rd = trd, st = tst;
rd = stdmax(rd, r[i]);
st += sum[i << 1 | 1];
vt[r[i]] = st;
dfs(i << 1, ss, zl);
}
else {
vt[r[i]] = 0;
st = 0;
dfs(i << 1, ss + sum[i << 1 | 1] + tst, r[i]);
st = tst, rd = trd;
if(a[b[i << 1]] >= rd) {
rd = stdmax(rd, r[i]);
vt[r[i]] = b[i << 1];
st += b[i << 1];
dfs(i << 1 | 1, ss, zl);
}
else {
int tp = stdmax(r[i], a[b[i << 1]]) + 1;
vt[r[i]] = tp >= zl ? 0 : vt[tp];
dfs(i << 1 | 1, ss, zl);
}
}
vt[r[i]] = 0;
rd = trd, st = tst;
}
void solve() {
build();
for(int i = 1; i < t; i <<= 1)
if(s[r[i]][id[i]] == '0')
if(b[i] == b[i << 1])
std::fill(ans + lp[i << 1 | 1] - 1, ans + rp[i << 1 | 1], b[i]);
else {
vt[r[i]] = 0;
rd = st = 0;
dfs(i << 1 | 1, 0, 20);
}
else {
rd = r[i];
st = vt[r[i]] = b[i << 1];
dfs(i << 1 | 1, 0, 20);
}
LL val = 0;
for(int i = 1, x; i <= m; ++i) {
for(x = 0; (1 << x) < c[i]; ++x) ;
LL v = (1 << x) == c[i] ? b[t / c[i]] : ans[c[i]];
val ^= i * v;
}
printf("%lld\n", val);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &aa[i]);
for(int i = 1; i <= m; ++i)
scanf("%d", &c[i]);
for(t = n; t & (t - 1); t += t & -t) ;
for(int i = 1; (1 << i) <= t; ++i)
scanf("%s", s[i]);
int cases;
scanf("%d", &cases);
while(cases--) {
int x[4];
scanf("%d%d%d%d", &x[0], &x[1], &x[2], &x[3]);
for(int i = 1; i <= n; ++i)
a[i] = aa[i] ^ x[i & 3];
solve();
}
return 0;
}