考虑只有一次询问的时候怎么做。
显然的 cdq 分治，每次分治区间 \([l,r]\)，统计跨过 \(p=\lfloor\frac{l+r}{2}\rfloor\) 的区间的个数。可以枚举区间左端点，由于右端点右移时区间或单调非降，可以双指针维护。
充分发掘题目条件，由于是区间或，还有一个很套路的性质：一个位置 \(x\)，以其为左端点的区间 \([x,r]\) 的或和取值个数不超过 \(\log w\) 个。这是显然的，因为每次区间或更改，至少使 \(1\) 个位置从 \(0\) 变成 \(1\)。同理，以 \(x\) 为左端点的区间 \([l,x]\) 的或和取值个数也不超过 \(\log w\) 个，所以经过 \(x\) 的区间 \([l,r]\) 的或和取值个数就不超过 \(\log^2 w\) 个了。
这启示我们使用线段树维护。根据刚才分治的思路，只要我们得到经过 \(p\) 的合法区间个数，不难向左右递归求解。而我们现在考虑把这个过程纳入线段树节点合并之中。
具体来讲，每个线段树节点开 \(2\) 个数组 \(pr,sf\)，\(pr_i\) 表示从左到右第 \(i\) 个前缀或值不同点，\(sf_i\) 表示从右到左第 \(i\) 个后缀数值不同点。合并的时候是 \(O(\log^2 w)\) 的，但是卡不满，复杂度 \(O(n\log n\log^2w)\)。可以二分/双指针优化至 \(O(n\log n\log w\log\log w)/O(n\log n\log w)\)，但是懒得写了。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define rd read
#define wr write
#define pc putchar
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(ll x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int N = 1e5 + 100;
int n, m, v, a[N];
struct seg {
vector<pi> pr, sf;// (val, pos) size <= 20
ll cnt;
int lp, rp;
seg operator + (const seg &rhs) const {
seg res;
res.cnt = cnt + rhs.cnt;
res.lp = lp, res.rp = rhs.rp;
for (int i = 0; i < sf.size(); i++) {
int j = 0;
while (j < rhs.pr.size() && (rhs.pr[j].fi | sf[i].fi) < v) j++;
if (j >= rhs.pr.size()) continue;
if (i == sf.size() - 1) res.cnt += 1ll * (sf[i].se - lp + 1) * (rhs.rp - rhs.pr[j].se + 1);
else res.cnt += 1ll * (sf[i].se - sf[i + 1].se) * (rhs.rp - rhs.pr[j].se + 1);
}
res.pr = pr;
int lst = pr.rbegin() -> fi;
for (pi p : rhs.pr) {
int cur = lst | p.fi;
if (cur ^ lst) res.pr.pb(mp(cur, p.se));
lst = cur;
}
res.sf = rhs.sf;
lst = rhs.sf.rbegin() -> fi;
for (pi p : sf) {
int cur = lst | p.fi;
if (cur ^ lst) res.sf.pb(mp(cur, p.se));
lst = cur;
}
return res;
}
} tr[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void pushup(int x) { tr[x] = tr[ls] + tr[rs]; }
void build(int l, int r, int x) {
if (l == r) {
vector<pi> tp; tp.pb(mp(a[l], l));
tr[x] = (seg) { tp, tp, (a[l] >= v), l, r };
return;
}
build(l, mid, ls), build(mid + 1, r, rs), pushup(x);
}
void upd(int l, int r, int p, int c, int x) {
if (l == r) {
vector<pi> tp; tp.pb(mp(c, l));
tr[x] = (seg) { tp, tp, (c >= v), l, r };
return;
}
if (p <= mid) upd(l, mid, p, c, ls);
else upd(mid + 1, r, p, c, rs);
pushup(x);
}
seg qry(int l, int r, int s, int t, int x) {
if (s <= l && r <= t) return tr[x];
if (t <= mid) return qry(l, mid, s, t, ls);
else if (s > mid) return qry(mid + 1, r, s, t, rs);
else return qry(l, mid, s, t, ls) + qry(mid + 1, r, s, t, rs);
}
signed main() {
n = rd(), m = rd(), v = rd();
for (int i = 1; i <= n; i++) a[i] = rd();
build(1, n, 1);
while (m--) {
int op = rd(), l = rd(), r = rd();
if (op == 1) upd(1, n, l, r, 1);
else wr(qry(1, n, l, r, 1).cnt), puts("");
}
return 0;
}