题解：P4883 mzf的考验

· · 题解

这是一道数据结构题。

前置知识

思路

看到区间翻转我们可以立刻想到平衡树，但是如何维护区间异或和区间求和呢？

我们考虑对于每个二进制位都开一棵平衡树，也可以在一棵平衡树上维护每个位的 1 的数量，我用的是后者，因为后者的时间是更快的，空间也是更小的，可以共用大小、懒标记等。

我们考虑如何快速维护区间翻转、区间异或、区间查询，我们需要维护什么东西？首先，大小、左儿子、右儿子肯定是需要的，其次，每位的 1 的数量之和以及当前点的 1 的数量之和也是需要的，最后，我们需要快速翻转、异或，所以需要区间异或、区间翻转懒标记。

我们考虑如何区间翻转，我们将这个区间分裂出来，然后将翻转标记异或上 1，下传时，如果当前节点有翻转懒标记，我们就交换左右儿子，然后将左右儿子的翻转标记也异或上 1。

然后是区间异或，我们将异或的数拆成一个长度为 20 的数组，表示当前位是不是 1，异或懒标记同理，然后我们将区间分裂出来，将异或懒标记每位都异或上这个数组，如果这个数组（不是懒标记）的第 i 位为 1，那么我们就将 sum_{i} 改为 siz - sum_{i}（sum_{i} 为每一位为 1 的总数，siz 为节点代表的区间大小，当前节点的值同样修改），下传的时候同理，将左右儿子的懒标记同样异或上当前节点的懒标记。

关于区间翻转和区间异或懒标记下传的顺序其实不重要，不会互相影响。

上传的时候就直接将和相加，并加上当前节点的值，节点大小同理更新。

当前节点值也可以直接用 int 存储，然后直接异或，上传时再取出这一位，我的代码用的是数组存储。

区间查询时就直接分裂出这一个区间，然后将每一位的值乘上 2^i 求和即可。

时间复杂度是 O((n+m) \log n \log V)，可以用 bitset 代替 bool 数组（前文的懒标记），可以加快速度，但是不改变总体时间复杂度。

Code

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n,Q,dat[N],res[20];
namespace Treap{
    struct node{
        int l,r,rnd,val[20],sum[20],siz;
        bool rev,tag[20];
    } tri[N];
    int tot,root;
    int new_node(){
        int p = ++ tot;
        for(int i = 0;i < 20;i ++){
            tri[p].val[i] = tri[p].sum[i] = res[i];
        }
        tri[p].rnd = rand();
        tri[p].siz = 1;
        return p;
    }
    void pushup(int p){
        tri[p].siz = tri[tri[p].l].siz + tri[tri[p].r].siz + 1;
        for(int i = 0;i < 20;i ++){
            tri[p].sum[i] = tri[tri[p].l].sum[i] + tri[tri[p].r].sum[i] + tri[p].val[i];
        }
    }
    void pushdown(int p){
        if(tri[p].rev == true){
            swap(tri[p].l,tri[p].r);
            if(tri[p].l != 0){
                tri[tri[p].l].rev ^= true;
            }
            if(tri[p].r != 0){
                tri[tri[p].r].rev ^= true;
            }
            tri[p].rev = false;
        }
        for(int i = 0;i < 20;i ++){
            if(tri[p].tag[i] == true){
                if(tri[p].l != 0){
                    tri[tri[p].l].tag[i] ^= true;
                    tri[tri[p].l].val[i] ^= 1;
                    tri[tri[p].l].sum[i] = tri[tri[p].l].siz - tri[tri[p].l].sum[i];
                }
                if(tri[p].r != 0){
                    tri[tri[p].r].tag[i] ^= true;
                    tri[tri[p].r].val[i] ^= 1;
                    tri[tri[p].r].sum[i] = tri[tri[p].r].siz - tri[tri[p].r].sum[i];
                }
                tri[p].tag[i] = false;
            }
        }
    }
    void split(int p,int k,int &x,int &y){
        if(p == 0){
            x = y = 0;
            return;
        }
        pushdown(p);
        if(tri[tri[p].l].siz >= k){
            y = p;
            split(tri[p].l,k,x,tri[p].l);
        }else{
            x = p;
            split(tri[p].r,k - tri[tri[p].l].siz - 1,tri[p].r,y);
        }
        pushup(p);
    }
    int merge(int x,int y){
        if(x == 0 or y == 0){
            return x + y;
        }
        if(tri[x].rnd < tri[y].rnd){
            pushdown(x);
            tri[x].r = merge(tri[x].r,y);
            pushup(x);
            return x;
        }else{
            pushdown(y);
            tri[y].l = merge(x,tri[y].l);
            pushup(y);
            return y;
        }
    }
    void add(){
        root = merge(root,new_node());
    }
    void reverse(int l,int r){
        int x,y,z;
        split(root,l - 1,x,y);
        split(y,r - l + 1,y,z);
        tri[y].rev ^= true;
        root = merge(merge(x,y),z);
    }
    void update(int l,int r){
        int x,y,z;
        split(root,l - 1,x,y);
        split(y,r - l + 1,y,z);
        for(int i = 0;i < 20;i ++){
            if(res[i] == true){
                tri[y].tag[i] ^= true;
                tri[y].val[i] ^= 1;
                tri[y].sum[i] = tri[y].siz - tri[y].sum[i];
            }
        }
        root = merge(merge(x,y),z);
    }
    void query(int l,int r){
        int x,y,z;
        split(root,l - 1,x,y);
        split(y,r - l + 1,y,z);
        for(int i = 0;i < 20;i ++){
            res[i] = tri[y].sum[i];
        }
        root = merge(merge(x,y),z);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> Q;
    for(int i = 1;i <= n;i ++){
        cin >> dat[i];
        for(int j = 0;j < 20;j ++){
            res[j] = (dat[i] >> j) & 1;
        }
        Treap::add();
    }
    while(Q --){
        int opt,l,r;
        cin >> opt >> l >> r;
        if(opt == 1){
            Treap::reverse(l,r);
        }else if(opt == 2){
            int k;
            cin >> k;
            for(int i = 0;i < 20;i ++){
                res[i] = (k >> i) & 1;
            }
            Treap::update(l,r);
        }else{
            Treap::query(l,r);
            ll ans = 0;
            for(int i = 0;i < 20;i ++){
                ans += (1ll << i) * (ll)(res[i]);
            }
            cout << ans << "\n";
        }
    }
    return 0;
}