P12500 XOR and OR

一道很好玩的题。

看到题的第一反映是拆位，拆完位就很好做了，先取反，可以转化成求所有子区间权值按位与的异或和。

维护一下前缀后缀

1

和

0

的长度，合并的时候答案加上左边的后缀乘右边的前缀，就可以了，答案就是区间所有子区间权值按位与的和的奇偶性。

具体地：

$pre_{0/1}$ 表示前缀极长 $0/1$ 的长度（表示反转之后 / 之前前缀极长 $0$ 的奇偶性）。
$suf_{0/1}$ 表示后缀极长 $0/1$ 的长度（表示反转之后 / 之前后缀极长 $0$ 的奇偶性）。
$ans_{0/1}$ 表示反转之后 / 之前的的答案。

但是你发现这只有

25

分。超空间了很难受。

考虑优化空间，你发现我只在乎奇偶性，所以

pre_{0/1}

、

suf_{0/1}

、

ans_{0/1}

都是 bool 型，这样就不会超空间了。

但还是过不了，因为时间复杂度是

O(n \log n \log V)

的。

这时你发现，这些全是 bool 型的，真的有必要全部分开算吗？

你发现我只要能把我所有 bool 的转移换成位运算，就可以全部一起算（因为位与位直接互不影响）。

于是你不拆位了，考虑把这些东西全部一起算。

$pre_{0/1}$ 的第 $i$ 位表示第 $i$ 位前缀极长 $0/1$ 的奇偶性（表示反转之后 / 之前前缀极长 $0$ 的奇偶性）。
$suf_{0/1}$ 的第 $i$ 位表示第 $i$ 位后缀极长 $0/1$ 的奇偶性（表示反转之后 / 之前后缀极长 $0$ 的奇偶性）。
$ans_{0/1}$ 的第 $i$ 位表示第 $i$ 位表示反转之后 / 之前的答案奇偶性。
$and_{0/1}$ 表示反转之后 / 之前的区间与（为了方便转移 $pre$ 和 $suf$ ）。

合并

再强调一次：只要能把我所有 bool 的转移换成位运算，就可以全部一起算。

CPP

node merge(node a,node b){
    if(a.And0 == (1ll << 60) - 1 && a.And1 == (1ll << 60) - 1)return b;//这个无所谓，用来判掉a为空
    node c;
    c.pre1 = a.pre1 ^ (b.pre1 & a.And0);
    c.suf1 = b.suf1 ^ (a.suf1 & b.And0);
    c.pre0 = a.pre0 ^ (b.pre0 & a.And1);
    c.suf0 = b.suf0 ^ (a.suf0 & b.And1);
    c.ans1 = (a.ans1 ^ b.ans1 ^ (a.suf1 & b.pre1));
    c.ans0 = (a.ans0 ^ b.ans0 ^ (a.suf0 & b.pre0));
    c.And0 = a.And0 & b.And0;
    c.And0 = a.And1 & b.And1;
    return c;
}

首先： pre , suf 的转移。

CPP

c.pre1 = a.pre1 ^ (b.pre1 & a.And0);
c.suf1 = b.suf1 ^ (a.suf1 & b.And0);
c.pre0 = a.pre0 ^ (b.pre0 & a.And1);
c.suf0 = b.suf0 ^ (a.suf0 & b.And1);

假设它是 bool 你会怎么写？

CPP

c.pre1 = (a.And0 ? (a.pre1 ^ b.pre1) : a.pre1);

对吧？

翻译成人话就是如果

a

管辖的区间全是 1 ，那么还要算上后面的贡献。

再看这个：

CPP

c.pre1 = a.pre1 ^ (b.pre1 & a.And0);

具体一点：

a.And0 是 1 ，那么这一位就是 (a.pre1 ^ b.pre1) 。

a.And0 是 0 ，那么这一位就是 (a.pre1 ^ (b.pre1 & 0)) 也就是 a.pre1 。

发现了吗？和上面那个是完全等价的，于是我们就成功的替换成位运算了。

其次：ans 的转移。

CPP

c.ans1 = (a.ans1 ^ b.ans1 ^ (a.suf1 & b.pre1));
c.ans0 = (a.ans0 ^ b.ans0 ^ (a.suf0 & b.pre0));

假设它是 bool 你会怎么写？

CPP

c.ans1 = (a.ans1 ^ b.ans1 ^ (a.suf1 * b.pre1));

其实在 bool 中 * 和 & 是一样的，所有直接替换就行了。

最后：And 的转移。

本来就是位运算。

下传标记

接着就是要整体异或上一个值。

因为我们处理了一个数每一位取反后的值，所有我们其实是要交换某些位。

CPP

void Swap(int &a,int &b,int x){
    int v = (a & x) ^ (b & x);
    a ^= v , b ^= v;
}

假设它是 bool 你会怎么写？

CPP

void Swap(bool &a,bool &b,bool x){
    if(x)swap(a , b);
}

我们知道，swap 可以换成下面这样。

CPP

void Swap(bool &a,bool &b,bool x){
    if(x){
        int t = a ^ b;
        a ^= t , b ^= t;
        //a ^= b ^= a ^= b;
    }
}

我们希望

x = 0

时可以直接让

a , b

不交换，也就是让

t = 0

。

于是：

CPP

void Swap(bool &a,bool &b,bool x){
    int t = (x & a) ^ (x & b);
    a ^= t , b ^= t;
}

有了这个东西，下传标记就很简单了。

CPP

void Xor(node &rt , int x){
    Swap(rt.pre0 , rt.pre1 , x);
    Swap(rt.suf0 , rt.suf1 , x);
    Swap(rt.And0 , rt.And1 , x);
    Swap(rt.ans0 , rt.ans1 , x);
    return ;
}
void down(int u){
    if(lazy[u]){
        lazy[u << 1] ^= lazy[u] , lazy[u << 1 | 1] ^= lazy[u];
        Xor(tree[u << 1] , lazy[u]) , Xor(tree[u << 1 | 1] , lazy[u]);
        lazy[u] = 0;
    }
}

于是，本来要 60 次现在用一次位运算解决了。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
#define f(i , l , r) for(int i = (l);i <= (r);++ i)
#define d(i , l , r) for(int i = (r);i >= (l);-- i)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define sc second
#define lowbit(x) ((x)&-(x))
#define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
const int N = 5e5 + 10;
int n , q , a[N] , lazy[N<<2];
struct node{
    int suf1 , pre1 , suf0 , pre0 , ans1 , ans0 , And0 , And1;
}tree[N<<2];
node merge(node a,node b){
    if(a.And0 == (1ll << 60) - 1 && a.And1 == (1ll << 60) - 1)return b;
    node c;
    c.pre1 = a.pre1 ^ (b.pre1 & a.And0);
    c.suf1 = b.suf1 ^ (a.suf1 & b.And0);
    c.pre0 = a.pre0 ^ (b.pre0 & a.And1);
    c.suf0 = b.suf0 ^ (a.suf0 & b.And1);
    c.ans1 = (a.ans1 ^ b.ans1 ^ (a.suf1 & b.pre1));
    c.ans0 = (a.ans0 ^ b.ans0 ^ (a.suf0 & b.pre0));
    c.And0 = a.And0 & b.And0;
    c.And0 = a.And1 & b.And1;
    return c;
}
void up(int u){
    tree[u] = merge(tree[u << 1] , tree[u << 1 | 1]);
}
void Swap(int &a,int &b,int x){
    int v = (a & x) ^ (b & x);
    a ^= v , b ^= v;
}
void Xor(node &rt , int x){
    Swap(rt.pre0 , rt.pre1 , x);
    Swap(rt.suf0 , rt.suf1 , x);
    Swap(rt.And0 , rt.And1 , x);
    Swap(rt.ans0 , rt.ans1 , x);
    return ;
}
void down(int u){
    if(lazy[u]){
        lazy[u << 1] ^= lazy[u] , lazy[u << 1 | 1] ^= lazy[u];
        Xor(tree[u << 1] , lazy[u]) , Xor(tree[u << 1 | 1] , lazy[u]);
        lazy[u] = 0;
    }
}
void input(int u,int l,int r,int L,int R,int x){
    if(L <= l&&r <= R){
        Xor(tree[u] , x);
        lazy[u] ^= x;
        return ;
    }
    int mid = l + r >> 1;down(u);
    if(L <= mid)input(u << 1 , l , mid , L , R , x);
    if(R > mid)input(u << 1 | 1 , mid + 1 , r , L , R , x);
    return up(u);
}
node query(int u,int l,int r,int L,int R){
    if(L <= l && r <= R)return tree[u];
    int mid = l + r >> 1;node res = {0 , 0 , 0 , 0 , 0 , 0 , (1ll << 60) - 1 , (1ll << 60) - 1};
    down(u);
    if(L <= mid)res = merge(res , query(u << 1 , l , mid , L , R));
    if(R > mid)res = merge(res , query(u << 1 | 1 , mid + 1 , r , L , R));
    return res;
}
void build(int u,int l,int r){
    if(l == r){
        tree[u] = {a[l] , a[l] , a[l] ^ (1ll << 60) - 1 , a[l] ^ (1ll << 60) - 1 , a[l] , a[l] ^ (1ll << 60) - 1 , a[l] , a[l] ^ (1ll << 60) - 1};
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1 , l , mid);
    build(u << 1 | 1 , mid + 1 , r);
    return up(u);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    cin >> n >> q;
    f(i , 1 , n)cin >> a[i] , a[i] ^= (1ll << 60) - 1;
    build(1 , 1 , n);
    f(i , 1 , q){
        int l , r , x , op;
        cin >> op >> l >> r;
        if(op == 1)cin >> x , input(1 , 1 , n , l , r , x);
        else cout << (query(1 , 1 , n , l , r).ans1 ^ (((r - l + 1) * (r - l + 2) / 2 & 1) ? (1ll << 60) - 1 : 0ll)) << "\n";
    }
}

P12500 XOR and OR

文章操作

P12500 XOR and OR

合并

下传标记

相关推荐

评论

P12500 XOR and OR