题解：P12500 「DLESS-1」XOR and OR

· · 题解

\color{blue}{\texttt{[Analysis]}}

显然，一般的位运算的题目都是需要拆位考虑的。

位运算最大的特点就是按位运算，没有进位和退位，所以按位考虑是很常见的思路。

而按位考虑最大的优势就是每一位数只有 0 和 1，情况最多 4 种组合，考虑起来方便很多。

考虑修改操作，异或上 0 等于没变，异或上 1 等于 01 反转。

考虑询问操作，对于一个区间 [l,r]，其按位或结果为 0 当且仅当区间内所有数都是 0。而异或为 1 当且仅当有奇数个 1 在异或。

于是询问操作等价于询问区间 [l,r] 内有多少个子区间 [x,y]（即 l \leq x \leq y \leq r），满足 a_{x \dots y} 中不全为 0。最后的结果取决于这个值的奇偶性。

显然，不全为并不是一个很方面考虑的命题，相反，它的否命题全为考虑起来更加方便。

正难则反，不全为 0 的区间个数等于总数减去全为 0 的区间个数。

于是需要维护一下几个量：

为了书写方便，下面分别用 a,b,c,d 表示上面的四个量。

合并两个区间 (a_{1},b_{1},c_{1},d_{1}),(a_{2},b_{2},c_{2},d_{2}) 时，有如下转移：

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)。

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;
}