题解 CF242E 【XOR on Segment】

发表于 | 更新于 | 阅读次数：

一道模拟赛的题

题目中给定的数值都是小于1e6的，

那么我们就可以暴力把线段树上的每个点拆成二进制表达，也就是20位，线段树上的每个点的二进制表示这个区间这位二进制为1的数量。

建树就非常简单，考虑懒标记和查询还有修改。

我们知道异或是满足分配率的，即（x^y）^c=x^(y^c);

那么我们就可以用懒标记来维护异或值；

每次修改区间，我们再暴力拆开异或值，如果一位是1，那么这个区间的这个位上的1就等于$(r-l+1)-f[i][k]$;

懒标记就是直接异或上一层懒标记同时对这个区间进行修改就行了

查询的时候把下面的两个区间的1的数量相加就行。

最后得到答案的时候再把二进制转回来就行了。

复杂度$ O(20nlogn) $ ???
算了还是 $ O(能过)$

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int L=1000000;
char ppp[L];
char *p1,*p2;
inline char gc()
{
    if(p1==p2)
    {
        p2=(p1=ppp)+fread(ppp,1,L,stdin);
    }
    return *p1++;
}
#define getchar gc
inline void read(int &x)
{
    x=0;
    char ch=getchar();
    int pd=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            pd=-pd;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=pd;
    
}
inline void write(const int &x)
{
    int tmp=x;
    char ggg[10001];
    int s=0;
    if(tmp==0)
    {
        putchar('0');
        return ;
    }
    if(tmp<0)
    {
        putchar('-');
        tmp=-tmp;
    }
    while(tmp>0)
    {
        ggg[s++]=tmp%10+'0';
        tmp/=10;
    }
    while(s>0)
    {
        putchar(ggg[--s]);
    }
}

const int N=1e5+10;
int f[21][1000010],n,m,a[N];
int tag[1000010];

void build(int k,int l,int r)
{
    if(l==r)
    {
        int hh=a[l];
        for(register int i=0;i<=20;++i)
        {
            f[i][k]=hh&1;
            hh>>=1;
        }
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    for(register int i=0;i<=20;++i)
    {
        f[i][k]=(f[i][k<<1]+f[i][k<<1|1]);
    }
}

void push_down(int k,int l,int r)
{
    tag[k<<1]^=tag[k];
    tag[k<<1|1]^=tag[k];
    int mid=(l+r)>>1;
    int hh=tag[k];
    for(register int i=0;i<=20;++i)
    {
        if((hh)&1)
        {
            f[i][k<<1]=(mid-l+1)-f[i][k<<1];
            f[i][k<<1|1]=(r-mid)-f[i][k<<1|1];
            
        }hh>>=1;
    }
    tag[k]=0;
}

void change (int k,int l,int r,int p,int q,int v)
{
    if(l>=p&&r<=q)
    {
        tag[k]^=v;
        int hh=v;
        for(register int i=0;i<=20;++i)
        {
            if(hh&1)
            {
                f[i][k]=(r-l+1)-f[i][k];
            }
			hh>>=1;
        }
        return ;
    }
    int mid=(l+r)>>1;
    push_down(k,l,r);
    if(p<=mid)
    {
        change(k<<1,l,mid,p,q,v);
    }
    if(q>mid)
    {
        change(k<<1|1,mid+1,r,p,q,v);
    }
    for(register int i=0;i<=20;++i)
    {
        f[i][k]=(f[i][k<<1]+f[i][k<<1|1]);
    }
    
}
struct dd
{
    int rs[21];
    void clear()
    {
        memset(rs,0,sizeof(rs));
    }
};
dd query(int k,int l,int r,int p,int q)
{
    if(l>=p&&r<=q)
    {
        dd ans;
        for(register int i=0;i<=20;++i)
        {
            ans.rs[i]=f[i][k];
        }
        return ans;
    }
    int mid=(l+r)>>1;
    dd ans;
    ans.clear();
    push_down(k,l,r);
    if(p<=mid)
    {
        dd now;
        now=query(k<<1,l,mid,p,q);
        for(register int i=0;i<=20;++i)
        {
            ans.rs[i]=now.rs[i];
        }
    }
    if(q>mid)
    {
        dd now;
        now=query(k<<1|1,mid+1,r,p,q);
        for(register int i=0;i<=20;++i)
        {
            ans.rs[i]+=now.rs[i];
        }
    }
    return ans;
}


signed main()
{
    read(n);
    for(register int i=1;i<=n;++i)
    {
        read(a[i]);
    }
    build(1,1,n);
    read(m);
    for(register int i=1;i<=m;++i)
    {
        int aa;
        read(aa);
        if(aa==1)
        {
            int ll,rr;
            read(ll);
            read(rr);
            dd ans=query(1,1,n,ll,rr);
            int last=0;
            for(register int i=0;i<=20;++i)
            {
                last+=(1<<i)*ans.rs[i];
            }
            write(last);
            puts("");
        }
        else 
        {
            int ll,rr,vv;
            read(ll);
            read(rr);
            read(vv);
            change(1,1,n,ll,rr,vv);
        }
    }
}