2log没有3log快

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
		ch=getchar();
	}
    return x;
}
void write(long long x){
    if(x>9){
        write(x/10);
	}
    putchar(x%10+'0');
}
int n,m,xx,s[100010];
struct node{
	long long ans;
	vector<pair<int,int> > l,r;
	vector<int> sl,sr;
};
struct segment_tree{
	node tree[400010];
	node merge(node &x,node &y){
		if(!x.l.size()){
			return y;
		}
		if(!y.l.size()){
			return x;
		}
		node res;
		res.ans=x.ans+y.ans;
		int j=y.l.size()-1;
		for(int i=0;i<x.r.size();i++){
//			printf("i %lld %lld\n",i,j);
			while(j&&(y.l[j-1].first|x.r[i].first)>=xx){
				j--;
			}
//			printf("j %lld\n",j);
			if((y.l[j].first|x.r[i].first)<xx){
				continue;
			}
			res.ans+=(long long)x.r[i].second*(y.sl[y.sl.size()-1]-(j?y.sl[j-1]:0ll));
//			printf("ans %lld\n",res.ans);
		}
//		printf("ans %lld\n",res.ans);
		res.l=x.l;
		int nows=res.l[res.l.size()-1].first;
		for(int i=0;i<y.l.size();i++){
			if((nows|y.l[i].first)!=nows){
				res.l.push_back({nows|y.l[i].first,y.l[i].second});
			}
			else{
				res.l[res.l.size()-1].second+=y.l[i].second;
			}
		}
		int ps=0;
		for(int i=0;i<res.l.size();i++){
			ps+=res.l[i].second;
			res.sl.push_back(ps);
		}
		res.r=y.r;
		nows=res.r[res.r.size()-1].first;
		for(int i=0;i<x.r.size();i++){
			if((nows|x.r[i].first)!=nows){
				res.r.push_back({nows|x.r[i].first,x.r[i].second});
			}
			else{
				res.r[res.r.size()-1].second+=x.r[i].second;
			}
		}
		ps=0;
		for(int i=0;i<res.r.size();i++){
			ps+=res.r[i].second;
			res.sr.push_back(ps);
		}
		return res;
	}
	void pushup(int index){
//		printf("pushup %lld\n",index);
		tree[index]=merge(tree[index<<1],tree[index<<1|1]);
	}
	void build(int left,int right,int index){
		if(left==right){
			tree[index].ans=(s[left]>=xx);
			tree[index].l={{s[left],1ll}};
			tree[index].r={{s[left],1ll}};
			tree[index].sl={1ll};
			tree[index].sr={1ll};
			return;
		}
		int mid=(left+right)>>1;
		build(left,mid,index<<1);
		build(mid+1,right,index<<1|1);
		pushup(index); 
	}
	void update(int g,int x,int left,int right,int index){
		if(g<left||right<g){
			return;
		}
		if(left==right){
			tree[index].ans=(x>=xx);
			tree[index].l={{x,1ll}};
			tree[index].r={{x,1ll}};
			tree[index].sl={1ll};
			tree[index].sr={1ll};
			return;
		}
		int mid=(left+right)>>1;
		update(g,x,left,mid,index<<1);
		update(g,x,mid+1,right,index<<1|1);
		pushup(index);
	}
	node search(int gleft,int gright,int left,int right,int index){
//		printf("search %lld %lld %lld %lld %lld\n",gleft,gright,left,right,index);
		if(gright<left||right<gleft){
			node res={0ll,{},{},{},{}};
			return res;
		}
		if(gleft<=left&&right<=gright){
			return tree[index];
		}
		int mid=(left+right)>>1;
		node resl=search(gleft,gright,left,mid,index<<1),resr=search(gleft,gright,mid+1,right,index<<1|1);
		return merge(resl,resr);
	}
}tr;
signed main(){
	n=read();
	m=read();
	xx=read(); 
	for(int i=1;i<=n;i++){
		s[i]=read();
	}
	tr.build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,x,y;
		op=read();
		x=read();
		y=read();
		if(op==1){
			tr.update(x,y,1,n,1);
		} 
		else{
			write(tr.search(x,y,1,n,1).ans);
			putchar('\n');
		}
	}
	return 0;
}

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
		ch=getchar();
	}
    return x;
}
void write(long long x){
    if(x>9){
        write(x/10);
	}
    putchar(x%10+'0');
}
int n,m,xx,s[100010];
struct node{
	long long ans;
	vector<pair<int,int> > l,r;
};
struct segment_tree{
	node tree[400010];
	node merge(node &x,node &y){
		if(!x.l.size()){
			return y;
		}
		if(!y.l.size()){
			return x;
		}
		node res;
		res.ans=x.ans+y.ans;
		for(int i=0;i<x.r.size();i++){
			for(int j=0;j<y.l.size();j++){
				if((x.r[i].first|y.l[j].first)>=xx){
					res.ans+=(long long)x.r[i].second*y.l[j].second;
				}
			}
		}
		res.l=x.l;
		int nows=res.l[res.l.size()-1].first;
		for(int i=0;i<y.l.size();i++){
			if((nows|y.l[i].first)!=nows){
				res.l.push_back({nows|y.l[i].first,y.l[i].second});
			}
			else{
				res.l[res.l.size()-1].second+=y.l[i].second;
			}
		}
		res.r=y.r;
		nows=res.r[res.r.size()-1].first;
		for(int i=0;i<x.r.size();i++){
			if((nows|x.r[i].first)!=nows){
				res.r.push_back({nows|x.r[i].first,x.r[i].second});
			}
			else{
				res.r[res.r.size()-1].second+=x.r[i].second;
			}
		}
		return res;
	}
	void pushup(int index){
		tree[index]=merge(tree[index<<1],tree[index<<1|1]);
	}
	void build(int left,int right,int index){
		if(left==right){
			tree[index].ans=(s[left]>=xx);
			tree[index].l={{s[left],1ll}};
			tree[index].r={{s[left],1ll}};
			return;
		}
		int mid=(left+right)>>1;
		build(left,mid,index<<1);
		build(mid+1,right,index<<1|1);
		pushup(index); 
	}
	void update(int g,int x,int left,int right,int index){
		if(g<left||right<g){
			return;
		}
		if(left==right){
			tree[index].ans=(x>=xx);
			tree[index].l={{x,1ll}};
			tree[index].r={{x,1ll}};
			return;
		}
		int mid=(left+right)>>1;
		update(g,x,left,mid,index<<1);
		update(g,x,mid+1,right,index<<1|1);
		pushup(index);
	}
	node search(int gleft,int gright,int left,int right,int index){
//		printf("search %lld %lld %lld %lld %lld\n",gleft,gright,left,right,index);
		if(gright<left||right<gleft){
			node res={0,{},{}};
			return res;
		}
		if(gleft<=left&&right<=gright){
			return tree[index];
		}
		int mid=(left+right)>>1;
		node resl=search(gleft,gright,left,mid,index<<1),resr=search(gleft,gright,mid+1,right,index<<1|1);
		return merge(resl,resr);
	}
}tr;
signed main(){
	n=read();
	m=read();
	xx=read();
	for(int i=1;i<=n;i++){
		s[i]=read();
	}
	tr.build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,x,y;
		op=read();
		x=read();
		y=read();
		if(op==1){
			tr.update(x,y,1,n,1);
		} 
		else{
			write(tr.search(x,y,1,n,1).ans);
			putchar('\n');
		}
	}
	return 0;
}