【Codeforces 1004F】Sonya and Bitwise OR
线段树。
题目大意：
给定一个数列 $a_1,a_2,a_3,\ldots,a_n$，以及一个数 $x$，要支持两个操作：
给定 $p,y$，将 $a_p$ 变成 $y$。
给定 $l,r$，问有多少对 $i,j$ 满足 $l\leq i\leq j\leq r$，且 $a_i,a_{i+1},a_{i+2},\ldots,a_j$ 的按位或结果大于等于 $x$。
题解：
考虑求出按位或结果小于 $x$ 的区间，然后用总数去减。
我们对每个位置 $i$，维护 $p_i$ 表示最小的满足 $k\sim i$ 的按位或结果不到 $x$ 的位置 $k$。由按位或运算的单调性可以得到，$p$ 是单调不降的。
考虑没有修改只有查询。对于区间 $[l,r]$，我们可以分成 $[l,m],[m+1,r]$，满足 $\forall i\in[l,m]$，有 $p_i\lt l$；$\forall i\in[m+1,r]$，有 $l\leq p_i$。这个 $m$ 可以二分出来。
那么对于 $i\in [l,m]$，它的贡献就是 $i-l+1$，这部分是一个等差数列，可以直接计算。
对于 $i\in[m+1,r]$，它的贡献是 $i-p_i+1$。我们可以直接求出 $ \sum i$，而 $p_i$ 的部分可以预处理前缀和进行计算。
那么如何求一个 $i$ 的 $p_i$ 的值呢？
我们发现，固定位置 $k$，考虑 $1\leq i\leq k$ 的所有 $i$，$[i,k]$ 区间的按位或的结果。这里的不同值只有 $\log x+1$ 种。
原因也很简单，每次变化肯定是若干个位从 $0$ 变成 $1$，然后就不会变回去了，所以至多变 $\log x$ 次。
所以我们对每个数，维护位置在它前面的每个二进制位的最后出现位置。然后对其排序后逐个加入，直至大于等于 $x$ 即可。时间复杂度 $O(n\log x\log\log x)$。
现在考虑修改的操作。
那么我们来考虑对 $k$ 位置的修改操作。对于 $k$ 位置本身的 $p$ 值，我们可以在知道每个位上一次出现的位置的情况下，直接在 $O(\log x\log\log x)$ 的复杂度里更新。使用 set 来存每个位的出现位置即可。时间复杂度 $O(\log n\log x)$。
对于 $k$ 前面的位置，它的 $p$ 值不会变化。对于 $k$ 后面的位置，考虑其 $p_i$ 的变化。
对于 $i\gt k$，$k+1$ 到 $i$ 的按位或的和的不同方案，也只有 $\log x+1$ 种，并且每种的出现位置是连续的。
我们考虑求助 $k+1\sim$ 的所有不同值以及其对应区间，然后考虑让它跨过 $k$ 并继续向前延伸。这个可以在 $O(\log^2 x)$ 里解决。当然可以用双指针在 $O(\log x)$ 里解决。
现在我们相当于要做至多 $\log x+1$ 次区间覆盖的操作。我们还要支持对 $p$ 的区间求和以及二分。使用线段树维护这个 $p$ 数组即可。
时间复杂度 $O((n+m)\log n\log x)$。
Code：
#include<cstdio>
#include<set>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int n,m,X,a[N];
set<int>pos[20];
int sta[22],top,stk[22],tk;
namespace sgt{
int cov[N<<2],mn[N<<2];LL s[N<<2];
inline void update(int o){
mn[o]=min(mn[o<<1],mn[o<<1|1]),s[o]=s[o<<1]+s[o<<1|1];
}
inline void pushdown(int o,int len){
int&x=cov[o];
cov[o<<1]=cov[o<<1|1]=mn[o<<1]=mn[o<<1|1]=x;
s[o<<1]=x*(LL)(len+1>>1),s[o<<1|1]=x*(LL)(len>>1),x=0;
}
void modify(int l,int r,int o,const int&L,const int&R,const int&val){
if(L<=l&&r<=R)cov[o]=mn[o]=val,s[o]=(r-l+1LL)*val;else{
if(cov[o])pushdown(o,r-l+1);
const int mid=l+r>>1;
if(L<=mid)modify(l,mid,o<<1,L,R,val);
if(mid<R)modify(mid+1,r,o<<1|1,L,R,val);
update(o);
}
}
LL query(int l,int r,int o,const int&L,const int&R){
if(L<=l&&r<=R)return s[o];
if(cov[o])pushdown(o,r-l+1);
const int mid=l+r>>1;LL res=0;
if(L<=mid)res=query(l,mid,o<<1,L,R);
if(mid<R)res+=query(mid+1,r,o<<1|1,L,R);
return res;
}
int find(int l,int r,int o,const int&v){
if(mn[o]>v)return 0;
if(l==r)return l;
if(cov[o])pushdown(o,r-l+1);
const int mid=l+r>>1;
int res=find(mid+1,r,o<<1|1,v);
if(res==0)res=find(l,mid,o<<1,v);
return res;
}
}
void modify(int p,int v){
for(int i=0;i<20;++i)if(a[p]>>i&1)pos[i].erase(p);
a[p]=v;
for(int i=0;i<20;++i)if(v>>i&1)pos[i].insert(p);
tk=top=0;
for(int i=0;i<20;++i){
auto it=pos[i].upper_bound(p);
if(it!=pos[i].end())sta[++top]=*it<<5|i;
if(it!=pos[i].begin())stk[++tk]=*--it<<5|i;
}
sort(sta+1,sta+top+1),sort(stk+1,stk+tk+1,greater<int>());
sta[top+1]=(n+1)<<5,stk[tk+1]=0,sta[0]=(p+1)<<5;
int t=(stk[1]>>5)+1,nw=0,zt=0;
for(int i=1;i<=tk;++i)zt|=1<<(stk[i]&31);
for(int i=0,it=tk;i<=top;++i){
int l=sta[i]>>5,r=(sta[i+1]>>5)-1;
if(i)nw|=1<<(sta[i]&31);
if(nw>X)break;
while(it&&(zt|nw)>X)zt^=1<<(stk[it--]&31);
int L=(stk[it+1]>>5)+1;
if(l<=r)
sgt::modify(1,n,1,l,r,L);
}
nw=v;
for(int i=1;i<=tk;++i){
nw|=1<<(stk[i]&31);
if(nw>X)break;
t=(stk[i+1]>>5)+1;
}
sgt::modify(1,n,1,p,p,t);
}
LL query(int l,int r){
int ps=sgt::find(1,n,1,l-1);
ps=max(ps,l-1),ps=min(ps,r);
LL ans=ps+1<=r?-sgt::query(1,n,1,ps+1,r):0;
ans+=r-ps;
ans+=(ps-l+2)*(ps-l+1LL)/2;
ans+=(r+ps+1LL)*(r-ps)/2;
ans=(r-l+1LL)*(r-l+2)/2-ans;
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&X),--X;
for(int i=1;i<=n;++i){
scanf("%d",a+i),top=0;
for(int w=0;w<20;++w){
if(a[i]>>w&1)pos[w].insert(i);
if(!pos[w].empty())sta[++top]=*pos[w].rbegin()<<5|w;
}
sort(sta+1,sta+top+1,greater<int>());
sta[top+1]=0;
int nw=0,L=(sta[1]>>5)+1;
for(int j=1;j<=top;++j){
nw|=1<<(sta[j]&31);
if(nw>X)break;
L=(sta[j+1]>>5)+1;
}
sgt::modify(1,n,1,i,i,L);
}
while(m--){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1)modify(l,r);else printf("%lld\n",query(l,r));
}
return 0;
}