BZOJ 3261: 最大异或和

给定一个非负整数序列 {a}，初始长度为 N。
有 M个操作，有以下两种操作类型：
1 、A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N+1。
2 、Q l r x：询问操作，你需要找到一个位置 p，满足 l<=p<=r，使得：
a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出最大是多少。

第一行包含两个整数 N ，M，含义如问题描述所示。
第二行包含 N个非负整数，表示初始的序列 A 。
接下来 M行，每行描述一个操作，格式如题面所述。

假设询问操作有 T个，则输出应该有 T行，每行一个整数表示询问的答案。

5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
对于测试点 1-2，N,M<=5 。
对于测试点 3-7，N,M<=80000 。
对于测试点 8-10，N,M<=300000 。
其中测试点 1, 3, 5, 7, 9保证没有修改操作。
对于 100% 的数据， 0<=a[i]<=10^7。

4
5
6

对于 100% 的数据， 0<=a[i]<=10^7 。

题解

可持久化Tire数,处理一些区间Xor最大值的问题.
我们把每个数从高位往低位插入可持久化Tire树.
查询的时候两颗树相减从高位往低位贪心的区就可以了

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=600010;
struct Btree{
    int lx,rx;
    int siz;
};
Btree tree[Maxn*25];
int tot;
int root[Maxn];
int pow2[25];
inline void copyTree(int x,int y){
    tree[x].lx=tree[y].lx;
    tree[x].rx=tree[y].rx;
    tree[x].siz=tree[y].siz;
}
inline int insert(int y,int val){
    int x=++tot;
    int ret=x;
    for (int i=23;i>=0;i--){
        copyTree(x,y);
        tree[x].siz++;
        int t=val&pow2[i];
        if (t){
            y=tree[y].rx;
            tree[x].rx=++tot;
            x=tree[x].rx;
        }else{
            y=tree[y].lx;
            tree[x].lx=++tot;
            x=tree[x].lx;
        }
        //copyTree(x,y);
        tree[x].siz=tree[y].siz+1;
    }
    return ret;
}
inline int query(int l,int r,int val){
    int ret=0;
    for (int i=23;i>=0;i--){
        int t=val&pow2[i];
        if (t){
            if (tree[tree[r].lx].siz-tree[tree[l].lx].siz){
                ret+=pow2[i];
                l=tree[l].lx;
                r=tree[r].lx;
            }else{
                l=tree[l].rx;
                r=tree[r].rx;
            }
        }else{
            if (tree[tree[r].rx].siz-tree[tree[l].rx].siz){
                ret+=pow2[i];
                l=tree[l].rx;
                r=tree[r].rx;
            }else{
                l=tree[l].lx;
                r=tree[r].lx;
            }
        }
    }
    return ret;
}
int n,m;
int num[Maxn];
int sum[Maxn];
char ord[10];
int main(){
    freopen("3261.in","r",stdin);
    freopen("3261.out","w",stdout);
    pow2[0]=1;
    for (int i=1;i<25;i++) pow2[i]=pow2[i-1]*2;
    scanf("%d%d",&n,&m);
    n++;
    num[1]=0;
    for (int i=2;i<=n;i++) scanf("%d",&num[i]);
    sum[1]=num[1];
    for (int i=2;i<=n;i++) sum[i]=sum[i-1]^num[i];
    for (int i=1;i<=n;i++) root[i]=insert(root[i-1],sum[i]);
    for (int i=1;i<=m;i++){
        scanf("%s",ord);
        if (ord[0]=='A'){
            n++;
            scanf("%d",&num[n]);
            sum[n]=sum[n-1]^num[n];
            root[n]=insert(root[n-1],sum[n]);
        }else{
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);
            printf("%d\n",query(root[l-1],root[r],sum[n]^v));
        }
    }
    return 0;
}

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

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=600010;

struct Btree{

int lx,rx;

int siz;

};

Btree tree[Maxn*25];

int tot;

int root[Maxn];

int pow2[25];

inline void copyTree(int x,int y){

tree[x].lx=tree[y].lx;

tree[x].rx=tree[y].rx;

tree[x].siz=tree[y].siz;

}

inline int insert(int y,int val){

int x=++tot;

int ret=x;

for (int i=23;i>=0;i--){

copyTree(x,y);

tree[x].siz++;

int t=val&pow2[i];

if (t){

y=tree[y].rx;

tree[x].rx=++tot;

x=tree[x].rx;

}else{

y=tree[y].lx;

tree[x].lx=++tot;

x=tree[x].lx;

}

//copyTree(x,y);

tree[x].siz=tree[y].siz+1;

}

return ret;

}

inline int query(int l,int r,int val){

int ret=0;

for (int i=23;i>=0;i--){

int t=val&pow2[i];

if (t){

if (tree[tree[r].lx].siz-tree[tree[l].lx].siz){

ret+=pow2[i];

l=tree[l].lx;

r=tree[r].lx;

}else{

l=tree[l].rx;

r=tree[r].rx;

}

}else{

if (tree[tree[r].rx].siz-tree[tree[l].rx].siz){

ret+=pow2[i];

l=tree[l].rx;

r=tree[r].rx;

}else{

l=tree[l].lx;

r=tree[r].lx;

}

return ret;

}

int n,m;

int num[Maxn];

int sum[Maxn];

char ord[10];

int main(){

freopen("3261.in","r",stdin);

freopen("3261.out","w",stdout);

pow2[0]=1;

for (int i=1;i<25;i++) pow2[i]=pow2[i-1]*2;

scanf("%d%d",&n,&m);

n++;

num[1]=0;

for (int i=2;i<=n;i++) scanf("%d",&num[i]);

sum[1]=num[1];

for (int i=2;i<=n;i++) sum[i]=sum[i-1]^num[i];

for (int i=1;i<=n;i++) root[i]=insert(root[i-1],sum[i]);

for (int i=1;i<=m;i++){

scanf("%s",ord);

if (ord[0]=='A'){

n++;

scanf("%d",&num[n]);

sum[n]=sum[n-1]^num[n];

root[n]=insert(root[n-1],sum[n]);

}else{

int l,r,v;

scanf("%d%d%d",&l,&r,&v);

printf("%d\n",query(root[l-1],root[r],sum[n]^v));

}

return 0;

}

WNJXYKの博客

喂你脚下有坑

BZOJ 3261: 最大异或和

Description

Input

Output

Sample Input

Sample Output

HINT

题解

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

2022年 5月
一	二	三	四	五	六	日
						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

BZOJ 3261: 最大异或和

Description

Input

Output

Sample Input

Sample Output

HINT

题解

扫一扫支付

评论 放弃治疗

评论放弃治疗