专栏文章
题解：P12500 「DLESS-1」XOR and OR
P12500题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mip1gk2p
- 此快照首次捕获于
- 2025/12/03 04:36 3 个月前
- 此快照最后确认于
- 2025/12/03 04:36 3 个月前
显然，一般的位运算的题目都是需要拆位考虑的。
位运算最大的特点就是按位运算，没有进位和退位，所以按位考虑是很常见的思路。而按位考虑最大的优势就是每一位数只有 和 ，情况最多 种组合，考虑起来方便很多。
考虑修改操作，异或上 等于没变，异或上 等于 反转。
考虑询问操作，对于一个区间 ，其按位或结果为 当且仅当区间内所有数都是 。而异或为 当且仅当有奇数个 在异或。
于是询问操作等价于询问区间 内有多少个子区间 （即 ），满足 中不全为 。最后的结果取决于这个值的奇偶性。
显然，不全为并不是一个很方面考虑的命题，相反，它的否命题全为考虑起来更加方便。
正难则反，不全为 的区间个数等于总数减去全为 的区间个数。
于是需要维护一下几个量：
- ：所有元素均为 的子区间数量。
- ：这一段区间开头连续的 的数量。
- ：这一段区间末尾连续的 的数量。
- ：这一段区间内是否全部为 ，是为 否则为 。
为了书写方便，下面分别用 表示上面的四个量。
合并两个区间 时，有如下转移：
a&=a_{1}+a_{2}+c_{1}\times b_{2}\\
b&=b_{1}+d_{1}\times b_{2}\\
c&=c_{2}+d_{2}\times c_{1}\\
d &=d_{1}\times d_{2}
\end{cases}$$
因为区间可能发生 $01$ 反转，于是需要维护对称量。
但是这样做是 $O(n\log n \log V)$ 的，其中 $V$ 是值域，会超时。
我们发现我们求出区间个数是多此一举的，毕竟我们最终只关心个数的奇偶性。理论上奇偶性只需要一个 $0/1$ 就完全足够表示。本质就是对 $2$ 取模嘛。
再认真考虑一下就会发现，在对 $2$ 取模意义下，加法相当于异或，乘法相当于按位与。不信可以枚举一下所有情况。
于是我们可以用 $0/1$ 表示该位最终的结果，即拆完位后有把该位的答案用该位的 $0/1$ 表达完全。因此可以一次性把 $60$ 位全部维护出来。
细节看代码。
总时间复杂度 $O(n \log n)$。
```cpp
struct node{
ll ans[2],pre[2],suf[2],And[2];
node(){
ans[0]=ans[1]=pre[0]=pre[1]=suf[0]=suf[1]=0;
And[0]=And[1]=(1ll<<60)-1;
}
};
node merge(node a,node b){
if (a.And[0]==((1ll<<60)-1)&&a.And[1]==((1ll<<60)-1))
return b;//a 没有初值就用 b
register node res;
res.ans[0]=a.ans[0]^b.ans[0]^(a.suf[0]&b.pre[0]);
res.ans[1]=a.ans[1]^b.ans[1]^(a.suf[1]&b.pre[1]);
//所有的加法换成异或，所有的乘法换成按位与，咋看咋别扭
res.pre[0]=a.pre[0]^(b.pre[0]&a.And[1]);
res.pre[1]=a.pre[1]^(b.pre[1]&a.And[0]);
res.suf[0]=b.suf[0]^(a.suf[0]&b.And[1]);
res.suf[1]=b.suf[1]^(a.suf[1]&b.And[0]);
res.And[0]=a.And[0]&b.And[0];
res.And[1]=a.And[1]&b.And[1];
return res;
}
void Swap(ll &a,ll &b,ll x){
ll tmp=(a&x)^(b&x);
a^=tmp;b^=tmp;
}//如果 x=0 代表没有变化，因此需要先用按位与把 x=0 的位屏蔽
//事实上这个 swap 函数的思路来源于两个数交换的位运算写法
void Xor(node &a,ll x){
Swap(a.ans[0],a.ans[1],x);
Swap(a.pre[0],a.pre[1],x);
Swap(a.suf[0],a.suf[1],x);
Swap(a.And[0],a.And[1],x);
}
class Segment_Tree{
public:
void clear(int n=0){
if (n==0){
memset(tree,0,sizeof(tree));
memset(tag,0,sizeof(tag));
memset(ls,0,sizeof(ls));
memset(rs,0,sizeof(rs));
rt=ndcnt=0;
}
else{
for(int i=1;i<=(n<<1);i++)
tag[i]=ls[i]=rs[i]=0;
rt=ndcnt=0;
}
}
void set_size(int n){
this->n=n;
clear(n);
}
Segment_Tree(){clear();}
void build(int n,ll *a){
set_size(n);
build(rt,1,n,a);
}
void modify(int l,int r,ll val){
modify(rt,1,n,l,r,val);
}
node query(int l,int r){
return query(rt,1,n,l,r);
}
private:
node tree[N<<1];
int ls[N<<1],rs[N<<1],rt,ndcnt,n;
ll tag[N<<1];
void pushup(int o){
tree[o]=merge(tree[ls[o]],tree[rs[o]]);
}
void pushdown(int o){
tag[ls[o]]^=tag[o];
tag[rs[o]]^=tag[o];
Xor(tree[ls[o]],tag[o]);
Xor(tree[rs[o]],tag[o]);
tag[o]=0;
}
void build(int &o,int l,int r,ll *a){
if (!o) o=++ndcnt;
if (l==r){
tree[o].pre[1]=tree[o].ans[1]=tree[o].suf[1]=tree[o].And[0]=a[l];
tree[o].pre[0]=tree[o].ans[0]=tree[o].suf[0]=tree[o].And[1]=a[r]^((1ll<<60)-1);
return;
}
int mid=(l+r)>>1;
build(ls[o],l,mid,a);
build(rs[o],mid+1,r,a);
return pushup(o);
}
void modify(int o,int l,int r,int p,int q,ll val){
if (p<=l&&r<=q){
Xor(tree[o],val);
tag[o]^=val;
return;
}
if (tag[o]) pushdown(o);
int mid=(l+r)>>1;
if (p<=mid) modify(ls[o],l,mid,p,q,val);
if (mid<q) modify(rs[o],mid+1,r,p,q,val);
return pushup(o);
}
node query(int o,int l,int r,int p,int q){
if (p<=l&&r<=q) return tree[o];
if (tag[o]) pushdown(o);
node res;int mid=(l+r)>>1;
if (p<=mid) res=merge(res,query(ls[o],l,mid,p,q));
if (mid<q) res=merge(res,query(rs[o],mid+1,r,p,q));
return res;
}
};
Segment_Tree sgt;
int n,q;ll a[N];
int main(){
n=read();q=read();
for(int i=1;i<=n;i++)
a[i]=read()^((1ll<<60)-1);
sgt.build(n,a);
for(int i=1;i<=q;i++){
int l,r,opt;
opt=read();l=read();r=read();
if (opt==1) sgt.modify(l,r,read());
else{
ll tmp=sgt.query(l,r).ans[1];
if ((1ll*(r-l+1)*(r-l+2)/2)&1)
tmp^=((1ll<<60)-1);
printf("%lld\n",tmp);
}
}
return 0;
}
```相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...