题意:
给你n个数,每次有两种操作:
1 l r v 表示a[i]=max(a[i],v)[l<=i<=r]
2 l r v 简单来说就是问你v和a[i](l<=i<=r)的异或和,得到x,然后输出多少个数含有x的最高位
题解:
对于第一个询问,首先如果要更新的区间的数参差不齐,那么在单点更新一次之后,下限就会上来,那么更新过的点我们想办法之后不要直接单点更新。
于是用mi表示当前区间的最小值是什么,num_mi表示当前区间最小值有多少个。
这样子如果我们接下来要被改变的一个区间的值都是相同的话,直接区间更新就行了,举个例子:
1 1000 1 1000 1 1000…
那么假设我要更新这个区间为2,直接在包含这个区间的对应的线段树的位置上将mi[root]=2,然后接下来push_down的时候将下面的值更新即可。
但是此时出现了一个问题:怎么检查当前区间要更新的值都是同一个
smi表示第二小的值。
如果第二小的值>当前的值的话,就表示可以直接更新这个区间。
于是相当于每个点最多只会被单点更新一次左右。
对于第二个询问,我们维护一下区间每一位的个数就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,M=30,inf=1e9;
int mi[N*4],smi[N*4],num_mi[N*4],num[N*4][M];
void push_up(int root){
for(int i=0;i<M;i++)
num[root][i]=num[root<<1][i]+num[root<<1|1][i];
mi[root]=min(mi[root<<1],mi[root<<1|1]);
num_mi[root]=(mi[root]==mi[root<<1])*num_mi[root<<1]+(mi[root]==mi[root<<1|1])*num_mi[root<<1|1];
smi[root]=min(smi[root<<1],smi[root<<1|1]);
if(mi[root<<1]!=mi[root<<1|1])
smi[root]=min(smi[root],max(mi[root<<1],mi[root<<1|1]));
}
void cal(int root,int v){
for(int i=0;i<M;i++)
if(mi[root]&(1<<i))
num[root][i]-=num_mi[root];
mi[root]=v;
for(int i=0;i<M;i++)
if(mi[root]&(1<<i))
num[root][i]+=num_mi[root];
}
void push_down(int root){
if(mi[root<<1]<mi[root])cal(root<<1,mi[root]);
if(mi[root<<1|1]<mi[root])cal(root<<1|1,mi[root]);
}
int a[N];
void build(int l,int r,int root){
if(l==r){
mi[root]=a[l];
num_mi[root]=1;
smi[root]=inf;
for(int i=0;i<M;i++)
if(a[l]&(1<<i))
num[root][i]=1;
return ;
}
int mid=l+r>>1;
build(l,mid,root<<1);
build(mid+1,r,root<<1|1);
push_up(root);
}
void update(int l,int r,int root,int ql,int qr,int v){
if(mi[root]>=v)return ;
if(l>=ql&&r<=qr&&v<smi[root]){
cal(root,v);
return ;
}
if(l==r){
cal(root,v);
return ;
}
push_down(root);
int mid=l+r>>1;
if(mid>=ql)
update(l,mid,root<<1,ql,qr,v);
if(mid<qr)
update(mid+1,r,root<<1|1,ql,qr,v);
push_up(root);
}
int sum[M];
void query(int l,int r,int root,int ql,int qr){
if(l>=ql&&r<=qr){
for(int i=0;i<M;i++)
sum[i]+=num[root][i];
return ;
}
push_down(root);
int mid=l+r>>1;
if(mid>=ql)
query(l,mid,root<<1,ql,qr);
if(mid<qr)
query(mid+1,r,root<<1|1,ql,qr);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,n,1);
while(m--){
int op,l,r,v;
scanf("%d%d%d%d",&op,&l,&r,&v);
if(op-2)update(1,n,1,l,r,v);
else {
memset(sum,0,sizeof(sum));
int x=v;
query(1,n,1,l,r);
for(int i=0;i<M;i++)
if(sum[i]&1)
x^=(1<<i);
if(x==0){
printf("0\n");
continue;
}
int top=log2(x);
printf("%d\n",sum[top]+((v>>top)&1));
}
}
return 0;
}