(CF242E)XOR on Segment

发表于 分类于 ， ，

原题链接

思路:

如果只是求和的话就是一个十分简单的线段树模板， 但是加上了异或操作以后一切都变得不一样了.

一个思路是把数字拆位 , 开 21 个线段树， 每个线段树表示区间内某二进制位上为 0/1 的数的个数.

拆位后异或便好做了：对于异或的数 x, 若某位为 1, 则对应线段树对应区间取反即可.

同时也可以求得区间和: 在每个线段树中找到对应区间 1 的个数后乘上该线段树代表位的位权， 然后相加即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <queue>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Mn(100005);

template<typename T>
void qrd(T& x) {
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + (c-'0');
        c = getchar();
    }
}

int n,m;
int a[Mn];

struct tnd {    //线段树结点
    int v[2];   //0/1个数
    bool tg;    //懒标记(取反)
    tnd *ls,*rs;    //左右子结点
}*rts[21],*nil,mem[Mn*80];  //根指针, 空结点指针, 可用空间
void init_nil() {   //初始化
    nil = mem;
    *nil = (tnd) {{0,0},false,nil,nil};
}
tnd* new_tnd() {    //新结点
    static int memcnt(0);
    mem[++memcnt] = *nil;
    return mem+memcnt;
}

void upd(tnd* rt) { //向上更新
    rt->v[0] = rt->ls->v[0] + rt->rs->v[0];
    rt->v[1] = rt->ls->v[1] + rt->rs->v[1];
}
void psd(tnd* rt) { //下放标记
    if(rt->tg) {
        swap(rt->ls->v[0],rt->ls->v[1]);
        swap(rt->rs->v[0],rt->rs->v[1]);
        rt->ls->tg ^= 1;
        rt->rs->tg ^= 1;
        rt->tg = false;
    }
}
//建树
void build(tnd*& rt,int l,int r,int i) {
    rt = new_tnd();
    if(l==r) {
        rt->v[(a[l]&(1<<i))!=0] = 1;
        return;
    }
    int mid((l+r)/2);
    build(rt->ls,l,mid,i);
    build(rt->rs,mid+1,r,i);
    upd(rt);
}
//修改
void mdf(tnd* rt,int l,int r,int ml,int mr) {
    if(l>=ml && r<=mr) {
        swap(rt->v[0],rt->v[1]);
        rt->tg ^= 1;
        return;
    }
    psd(rt);
    int mid((l+r)/2);
    if(ml<=mid) {
        mdf(rt->ls,l,mid,ml,mr);
    }
    if(mr>mid) {
        mdf(rt->rs,mid+1,r,ml,mr);
    }
    upd(rt);
}
//查询
LL qry(tnd* rt,int l,int r,int ql,int qr) {
    if(l>=ql && r<=qr) {
        return rt->v[1];
    }
    psd(rt);
    int mid((l+r)/2);
    LL ret(0);
    if(ql<=mid) {
        ret += qry(rt->ls,l,mid,ql,qr);
    }
    if(qr>mid) {
        ret += qry(rt->rs,mid+1,r,ql,qr);
    }
    return ret;
}

int main() {
    init_nil();
    qrd(n);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
    }
    for(int i(0);i<=20;++i) {
        build(rts[i],1,n,i);
    }
    qrd(m);
    while(m--) {
        int o;
        qrd(o);
        if(o==1) {
            int l,r;
            qrd(l), qrd(r);
            LL ans(0);
            for(int i(0);i<=20;++i) {
                ans += qry(rts[i],1,n,l,r)*(1ll<<i);
            }
            printf("%lld\n",ans);
        } else {
            int l,r,x;
            qrd(l), qrd(r), qrd(x);
            for(int i(0);i<=20;++i) {
                if(x&(1<<i)) {
                    mdf(rts[i],1,n,l,r);
                }
            }
        }
    }
    return 0;
}