$\LARGE{分析}$
观察到值域 $a \leq 2^{20}$ ,所以对于每一个区间的前缀或后缀 $OR$ 的变化次数不超过 $O(\log a)$ 次,所以考虑在线段树上维护使前缀或后缀 $OR$ 变化的位置。
若已知一个区间的前缀和后缀 $OR$ ,那么可以用双指针算法计算跨越左右两端的满足的子区间,再分别递归左右即可。
预处理时间复杂度 $O(n\log a)$ ,每次修改询问复杂度 $O(\log n \log a)$ 。
$\LARGE{实现}$
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N];
struct Node {
long long ans;
vector<pair<int, int>> pre, suf;
} tr[N * 4];
Node merge(Node L, Node R) {
Node U;
U.ans = L.ans + R.ans;
R.pre.push_back({R.suf[0].fi + 1, 0});
for (int l = L.suf.size() - 1, r = 0; r < R.pre.size() - 1; r ++ ) {
while ((L.suf[l].se | R.pre[r].se) >= x && l >= 0) l -- ;
if (l == -1) U.ans += 1ll * (L.suf[0].fi - L.pre[0].fi + 1) * (R.pre[r + 1].fi - R.pre[r].fi);
if (l < L.suf.size() - 1) U.ans += 1ll * (L.suf[l + 1].fi - L.pre[0].fi + 1) * (R.pre[r + 1].fi - R.pre[r].fi);
}
R.pre.pop_back();
U.pre = L.pre;
for (int i = 0; i < R.pre.size(); i ++ )
if ((U.pre.back().se | R.pre[i].se) != U.pre.back().se)
U.pre.push_back({R.pre[i].fi, U.pre.back().se | R.pre[i].se});
U.suf = R.suf;
for (int i = 0; i < L.suf.size(); i ++ )
if ((U.suf.back().se | L.suf[i].se) != U.suf.back().se)
U.suf.push_back({L.suf[i].fi, U.suf.back().se | L.suf[i].se});
return U;
}
void build(int u, int l, int r) {
if (l == r) {
tr[u].ans = (a[l] >= x);
tr[u].pre.push_back({l, a[l]});
tr[u].suf.push_back({l, a[l]});
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}
void modify(int u, int l, int r, int p, int k) {
if (l == r) {
tr[u].ans = (k >= x);
tr[u].pre[0] = {p, k};
tr[u].suf[0] = {p, k};
return;
}
int mid = l + r >> 1;
if (p <= mid) modify(u << 1, l, mid, p, k);
else modify(u << 1 | 1, mid + 1, r, p, k);
tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}
Node query(int u, int l, int r, int s, int t) {
if (s <= l && r <= t) return tr[u];
int mid = l + r >> 1;
if (s > mid) return query(u << 1 | 1, mid + 1, r, s, t);
if (t <= mid) return query(u << 1, l, mid, s, t);
Node L = query(u << 1, l, mid, s, t);
Node R = query(u << 1 | 1, mid + 1, r, s, t);
return merge(L, R);
}
int main() {
scanf("%d%d%d", &n, &m, &x);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
build(1, 1, n);
for (int i = 0; i < m; i ++ ) {
int op, p, q;
scanf("%d%d%d", &op, &p, &q);
if (op == 1) modify(1, 1, n, p, q);
else printf("%lld\n", query(1, 1, n, p, q).ans);
}
return 0;
}