洛谷 P4735 最大异或和

最大异或和

题目描述

给定一个非负整数序列 { a } \{a\} {a}，初始长度为$n$。

有 $m$ 个操作，有以下两种操作类型：

1. A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $n+1$。
2. Q l r x：询问操作，你需要找到一个位置 $p$，满足$l\le p\le r$，使得： $
   a[p] \oplus a[p+1] \oplus … \oplus a[N] \oplus x$ 最大，输出最大是多少。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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
3
4
5
6
7

样例输出 #1

4
5
6
1
2
3

提示

对于测试点 $1-2$，$N,M\le 5$。
对于测试点 $3-7$，$N,M\le 80000$。
对于测试点 $8-10$，$N,M\le 300000$。
其中测试点 $1,3,5,7,9$保证没有修改操作。
$0\le a[i]\le 10^7$。

分析：

这是一道可持久化trie树模板题，函数直接照着敲就行了。

可持久化trie树

代码：

#include

using namespace std;

const int N=6e5+10,M=50*N;

int s[N];

int tr[M][2],max_id[M];

int root[N],idx;

void insert(int k, int p, int q)//我这里把insert改成了迭代版. 这里可以更清晰看到, max_id其实就是当前”trie新加的部分”对应在s数组的位置
{
    max_id[q]=k;
    
    for(int i=23;i>=0;i--)
    {
        int v=s[k]>>i&1;
        
        if(p)tr[q][v^1]=tr[p][v^1];
        
        tr[q][v]=++idx;
        
        max_id[tr[q][v]]=k;
        
        q=tr[q][v];
        
		p=tr[p][v];
    }
}


void insert(int i, int k, int p, int q) 
{
    if(k<0)
    {
        max_id[q]=i;
        
        return ;
    }

    int v=s[i]>>k&1;
    
    if(p)tr[q][v^1]=tr[p][v^1];
    
    tr[q][v]=++idx;
    
    insert(i, k - 1, tr[p][v], tr[q][v]);

    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int p, int l, int c)
{
    for(int i = 23; i >= 0; i --)
    {
        int v = c >> i & 1;
        
        if(max_id[tr[p][v ^ 1]] >= l)p = tr[p][v ^ 1];
        else p = tr[p][v];
    }

    return c ^ s[max_id[p]];
}

int main()
{
    int n, m;
    
    scanf("%d%d", &n, &m);
    
    s[0] = 0;
    
    max_id[0] = -1;
    
    root[0] = ++ idx;

    insert(0, 0, root[0]);

    for(int i = 1; i <= n; i ++)
    {
        int x;
        
        scanf("%d", &x);
        
        root[i] = ++ idx;
        
        s[i] = s[i - 1] ^ x;
        
        insert(i, root[i - 1], root[i]);
    }

    while(m --)
    {
        char op[2];
        
        scanf("%s", op);
        
        if(*op == 'A')
        {
            int x;
            
            scanf("%d", &x);
            
            n ++;
            
            root[n] = ++ idx;
            
            s[n] = s[n - 1] ^ x;
            
            insert(n, root[n - 1], root[n]);
        }
        else
        {
            int l, r, x;
            
            scanf("%d%d%d", &l, &r, &x);
            
            printf("%d\n", query(root[r - 1], l - 1, s[n] ^ x));
        }
    }
    
    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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

我太蒻了，所以不能给大家详细的分析，请谅解······