题目大意
给定一个长度为(n)的序列(a_1,a_2,dots,a_n)和一个非负整数(x)。你需要支持(m)次操作。操作有两种：
- (1 i y)：把序列的第(i)个元素设为(y)，也就是(a_i:=y)。
- (2 l r)：求有多少对((L,R))满足(lleq Lleq Rleq r)且(a_l,dots a_r)按位或的和大于等于(x)。
数据范围：(1leq n,mleq 10^5,0leq x,a_i,y<2^{20})。(1leq ileq n)。(1leq lleq rleq n)。
本题题解
考虑只有一次询问时怎么做。
分治。每次考虑(L)位于左半边，(R)位于右半边的情况（也就是“跨过中点”的答案）。再分别递归左、右两边。计算跨过中点的答案时，可以先求出【左半边的(operatorname{or})值后缀和】和【右半边的(operatorname{or})值前缀和】。然后用two pointers求出满足条件的((L,R))数量，例如，可以枚举(R)，则左半边的(L)可选范围单调增加，也就是从最左边不断向右移。这样，不算递归，每次做two pointers的复杂度都是(O( ext{len}))的，一次询问总复杂度就是(O( ext{len}log ext{len}))。
现在要支持单点修改和多次查询。考虑用线段树来维护。
分治时的左、右两边，天然就是线段树的左、右节点，这有很多相似之处。但是我们面临的问题是：如果向分治时一样，维护出每个区间的前缀、后缀(operatorname{or})和，则一次修改、查询的复杂度，都高达(O(nlog n))，无法承受。
此时要用到最关键的一个性质：前缀、后缀的(operatorname{or})和，都只会分成(O(log a))个段，满足每段内值相同，不同段值不同。这是因为，前缀、后缀(operatorname{or})和，都是单调不下降的，每次增长，都至少多出一个为(1)的二进制位，所以最多增长(log_2 a)次，也就是只有(O(log a))个段。
考虑对线段上每个区间，用两个( exttt{vector})，分别维护该区间前缀、后缀(operatorname{or})和的这(O(log a))个段。同时，维护每个区间的答案（这个区间里有多少对((L,R))满足......）。合并两个区间（也就是线段树( exttt{push_up})操作）时，先继承左、右儿子内部的答案，再用two pointers的方法求出跨过中点的答案（这和分治时是一样的）。于是我们就能(O(log a))实现( exttt{push_up})操作。也就能(O(nlog a))建树（预处理）、(O(log nlog a))实现一次单点修改了。
查询时，线段树当前节点的区间，如果被查询的区间完全覆盖，直接返回维护好的答案；否则递归左、右儿子，再计算跨过中点的答案。所以单次查询也是(O(log nlog a))的。
总时间复杂度(O(nlog a+mlog nlog a))。
参考代码：
//problem:CF1004F
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=1e5;
int n,m,X,a[MAXN+5];
struct SegmentTree{
int tl[MAXN*4+5],tr[MAXN*4+5];
ll ans[MAXN*4+5];
vector<pii>pre[MAXN*4+5],suf[MAXN*4+5];//(pos,val)
void ck(int p){
assert(SZ(pre[p]) && pre[p][0].fi==tl[p]);
assert(SZ(suf[p]) && suf[p][0].fi==tr[p]);
}
void push_up(int p){
int ls=p<<1,rs=p<<1|1;ck(ls);ck(rs);
//1. ans
ans[p]=ans[ls]+ans[rs];
for(int i=0,j=SZ(suf[ls]);i<SZ(pre[rs]);++i){
int nxt=(i<=SZ(pre[rs])-2?pre[rs][i+1].fi:tr[p]+1);
//R in [pre[rs][i].fi,nxt)
while(j>0 && (suf[ls][j-1].se|pre[rs][i].se)>=X)
--j;
if(j!=SZ(suf[ls]))
ans[p]+=(ll)(suf[ls][j].fi-tl[p]+1) * (nxt-pre[rs][i].fi);
}
//2. pre
pre[p]=pre[ls];
for(int i=0;i<SZ(pre[rs]);++i){
if(pre[p].back().se != (pre[p].back().se | pre[rs][i].se)){
pre[p].pb(mk(pre[rs][i].fi,pre[p].back().se|pre[rs][i].se));
}
}
//3. suf
suf[p]=suf[rs];
for(int i=0;i<SZ(suf[ls]);++i){
if(suf[p].back().se != (suf[p].back().se | suf[ls][i].se)){
suf[p].pb(mk(suf[ls][i].fi,suf[p].back().se|suf[ls][i].se));
}
}
assert(SZ(pre[p])<=21);
assert(SZ(suf[p])<=21);
}
void build(int p,int l,int r){
tl[p]=l;tr[p]=r;
if(l==r){
ans[p]=(a[l]>=X);
pre[p].pb(mk(l,a[l]));
suf[p].pb(mk(l,a[l]));
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
void point_modify(int p,int l,int r,int pos,int v){
if(l==r){
ans[p]=(v>=X);
pre[p][0]=mk(l,v);
suf[p][0]=mk(l,v);
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
point_modify(p<<1,l,mid,pos,v);
else
point_modify(p<<1|1,mid+1,r,pos,v);
push_up(p);
}
ll query(int p,int l,int r,int ql,int qr){
assert(ql>=l);assert(qr<=r);
if(ql==l && qr==r)
return ans[p];
int mid=(l+r)>>1;
if(qr<=mid)
return query(p<<1,l,mid,ql,qr);
else if(ql>mid)
return query(p<<1|1,mid+1,r,ql,qr);
else{
ll res=query(p<<1,l,mid,ql,mid) + query(p<<1|1,mid+1,r,mid+1,qr);
int ls=p<<1,rs=p<<1|1;ck(ls);ck(rs);
int j=SZ(suf[ls])-1;
while(suf[ls][j].fi<ql)
--j;
assert(j>=0);
for(int i=0;i<SZ(pre[rs]) && pre[rs][i].fi<=qr;++i){
int nxt=(i<=SZ(pre[rs])-2?pre[rs][i+1].fi:tr[p]+1);
ckmin(nxt,qr+1);
if((suf[ls][j].se|pre[rs][i].se)<X)
continue;
while(j>0 && (suf[ls][j-1].se|pre[rs][i].se)>=X)
--j;
res+=(ll)(suf[ls][j].fi-ql+1) * (nxt-pre[rs][i].fi);
}
return res;
}
}
SegmentTree(){}
}T;
int main() {
cin>>n>>m>>X;
for(int i=1;i<=n;++i)cin>>a[i];
T.build(1,1,n);
while(m--){
int op;cin>>op;
if(op==1){
int i,y;cin>>i>>y;
T.point_modify(1,1,n,i,y);
}
else{
int l,r;cin>>l>>r;
cout<<T.query(1,1,n,l,r)<<endl;
}
}
return 0;
}