CF242E XOR on Segment

发表于 更新于 分类于

分 块 大 法 好

题面

给定一个长为$n$($n<=10^5$)的数组

数组里的数不超过$10^6$

有两种操作：

1:求sum$[l,r]$;

2:对$[l,r]$中的所有数和$x$异或

操作数$m<=5*10^4$

思路

挺好的一道题。

首先看到这题想到用一个数据结构来维护。

那是什么呢？线段树？分块？

都可以。

但考虑到一个问题——区间异或没有逆分配律。

那怎么办。显然一般的线段树与分块达不到我们的要求。

考虑把每一个数拆开，因为数组里的数不超过$10^6$，所以只需要拆$20$位就可以满足需要。

然后大力分块，每块维护当前这块数$1到20位$的$1$的个数与本块当前的标记$0或是1$。答案就是$[l,r]$中$[1,20]$位分别乘上$2的[1,20]$次方。

代码写得自认为很清楚了。

自己康康吧。

代码

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
#include<bits/stdc++.h>
#define LL int
using namespace std;
struct block{int sum[25],tag[25],l,r;}B[100005];
int N,Q,a[100005],len,tot,num[100005],p[25];
inline void Read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline void Xor(int l,int r,int x,int id)
{
    if (x==0) return;//如果是0就不用管了 
    if (num[l]==num[r]){for (int i=l;i<=r;i++) if (a[i]>>id&1) B[num[i]].sum[id]--,a[i]^=(1<<id);else B[num[i]].sum[id]++,a[i]^=(1<<id); }
    else
	{
    for (int i=l;i<=B[num[l]].r;i++) if (a[i]>>id&1) B[num[i]].sum[id]--,a[i]^=(1<<id);else B[num[i]].sum[id]++,a[i]^=(1<<id);
    for (int i=num[l]+1;i<=num[r]-1;i++) B[i].tag[id]^=1;
    for (int i=B[num[r]].l;i<=r;i++) if (a[i]>>id&1) B[num[i]].sum[id]--,a[i]^=(1<<id);else B[num[i]].sum[id]++,a[i]^=(1<<id);
	}
}
inline int ask(int l,int r,int id)
{
    int res=0;
    if (num[l]==num[r]){for (int i=l;i<=r;i++) if (B[num[i]].tag[id]^((a[i]>>id)&1)) res++;}
    else
    {
        for (int i=l;i<=B[num[l]].r;i++) if (B[num[i]].tag[id]^((a[i]>>id)&1)) res++; 
        for (int i=num[l]+1;i<=num[r]-1;i++) if (B[i].tag[id]==1) res+=len-B[i].sum[id];else res+=B[i].sum[id];//如果块的id位上标记为1，则1变0,0变1 
        for (int i=B[num[r]].l;i<=r;i++) if (B[num[i]].tag[id]^((a[i]>>id)&1)) res++;
    }
    return res;
}
int main()
{
	p[0]=1;
	for (int i=1;i<=20;i++) p[i]=p[i-1]*2;
    Read(N);
    for (int i=1;i<=N;i++) Read(a[i]);
	Read(Q);
    len=sqrt(N); tot=N/len; 
	if (N%len) tot++;
    for (int i=1;i<=tot;i++) B[i].l=len*(i-1)+1,B[i].r=len*i;
    B[tot].r=N;
    for (int i=1;i<=N;i++) num[i]=(i-1)/len+1;
    for (int id=0;id<=20;id++){for (int i=1;i<=N;i++) B[num[i]].sum[id]+=((a[i]>>id)&1);}
    while (Q--)
    {
        int opt,l,r,x;
        Read(opt);
        if (opt==1)
        {
        	Read(l),Read(r);
        	long long ans=0;
			for (int id=0;id<=20;id++) ans+=1LL*ask(l,r,id)*p[id]; 
			cout<<ans<<endl;
        }
        else 
        {
            Read(l),Read(r),Read(x);
            for (int id=0;id<=20;id++) Xor(l,r,x>>id&1,id);
        }   
    } 
    return 0;
}