和 CF1004F Sonya and Bitwise OR 很像。
考虑一次询问怎么做。考虑分治，每次只计算左端点在 \([l, mid]\)，右端点在 \([mid + 1, r]\) 的区间的贡献。对于每个 \(i \in [l, mid]\)，维护最小的 \(j \in [mid + 1, r]\) 使得 \([i, j]\) 的或 \(\ge v\)，那么 \(\max\limits_{k = i}^j a_k\) 对答案有贡献。
考虑带修怎么做。考虑套上线段树，利用线段树的分治结构，问题变成了如何合并两个区间的答案。
按位或有个很好的性质，就是前（或后）缀的或只会变化 \(O(\log V)\) 次。所以我们对于线段树上每个结点，维护前缀和后缀的或第一次变化的位置。
计算左端点在左结点，右端点在右结点的区间贡献，就枚举左结点所有后缀或第一次变化的位置作为左端点，双指针维护使得区间或 \(\ge v\) 的最靠左的右端点即可。
注意到 \(a\) 不变，可以使用 ST 表单次 \(O(1)\) 计算 \(a\) 的区间最大值。合并两个区间的复杂度为 \(O(\log V)\)。所以总时间复杂度为 \(O((n + q) \log n \log V)\)。
code
// Problem: D. Bitwise Paradox
// Contest: Codeforces - Codeforces Round 930 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1936/D
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int logn = 20;
ll n, m, q, a[maxn], b[maxn], f[logn][maxn];
inline ll qmax(int l, int r) {
int k = __lg(r - l + 1);
return max(f[k][l], f[k][r - (1 << k) + 1]);
}
struct node {
ll ans;
vector<pii> pre, suf;
node() {
ans = 0;
vector<pii>().swap(pre);
vector<pii>().swap(suf);
}
};
inline node operator + (const node &a, const node &b) {
node res;
res.ans = min(a.ans, b.ans);
res.pre = a.pre;
for (pii p : b.pre) {
if ((res.pre.back().scd | p.scd) != res.pre.back().scd) {
res.pre.pb(p.fst, res.pre.back().scd | p.scd);
}
}
res.suf = b.suf;
for (pii p : a.suf) {
if ((res.suf.back().scd | p.scd) != res.suf.back().scd) {
res.suf.pb(p.fst, res.suf.back().scd | p.scd);
}
}
int j = (int)b.pre.size() - 1;
for (pii p : a.suf) {
while (j && (p.scd | b.pre[j - 1].scd) >= m) {
--j;
}
if ((p.scd | b.pre[j].scd) >= m) {
res.ans = min(res.ans, qmax(p.fst, b.pre[j].fst));
}
}
return res;
}
namespace SGT {
node a[maxn << 2];
inline void pushup(int x) {
a[x] = a[x << 1] + a[x << 1 | 1];
}
void build(int rt, int l, int r) {
if (l == r) {
a[rt].ans = (b[l] >= m ? ::a[l] : 9e18);
a[rt].pre = a[rt].suf = vector<pii>(1, mkp(l, b[l]));
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int x, ll y) {
if (l == r) {
a[rt].ans = (y >= m ? ::a[l] : 9e18);
a[rt].pre = a[rt].suf = vector<pii>(1, mkp(l, y));
return;
}
int mid = (l + r) >> 1;
(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
pushup(rt);
}
node query(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return a[rt];
}
int mid = (l + r) >> 1;
if (qr <= mid) {
return query(rt << 1, l, mid, ql, qr);
} else if (ql > mid) {
return query(rt << 1 | 1, mid + 1, r, ql, qr);
} else {
return query(rt << 1, l, mid, ql, qr) + query(rt << 1 | 1, mid + 1, r, ql, qr);
}
}
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
f[0][i] = a[i];
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &b[i]);
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
}
}
SGT::build(1, 1, n);
scanf("%lld", &q);
while (q--) {
ll op, x, y;
scanf("%lld%lld%lld", &op, &x, &y);
if (op == 1) {
SGT::update(1, 1, n, x, y);
} else {
ll ans = SGT::query(1, 1, n, x, y).ans;
printf("%lld ", ans > 1e18 ? -1LL : ans);
}
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}