Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定一个非负整数序列 a，初始长度为 N。
有 M 个操作，有以下两种操作类型：
A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 增大 1。
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 行，每行描述一个操作，格式如题面所述。
输出格式
每个询问操作输出一个整数，表示询问的答案。
每个答案占一行。
数据范围
N,M≤3×105,0≤a[i]≤107。
输入样例：
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
输出样例：
4
5
6
#include<bits/stdc++.h>
using namespace std;
const int K = 25;
const int M = 6e6 + 10;
const int N = 6e6 + 10;
int trie[M * K][2],ctx;
int root[N],max_id[M * K];
int s[N];
int query(int l,int p,int C){
if(root == 0)return 0;
for(int i = 24;i >= 0;i --){
int a = ((C >> i) & 1);
if(trie[p][a ^ 1] && max_id[trie[p][a ^ 1]] >= l){
p = trie[p][a ^ 1];
}else {
p = trie[p][a];
}
}
return s[max_id[p]];
}
void insert(int bit,int x,int p,int q,int d){
if(bit < 0){
max_id[p] = d;
return;
}else{
int a = ((x >> bit) & 1);
if(q)trie[p][a ^ 1] = trie[q][a ^ 1];
trie[p][a] = ++ ctx;
int t = p;
q = trie[q][a],p = trie[p][a];
insert(bit - 1,x,p,q,d);
max_id[t] = max(max_id[trie[t][0]],max_id[trie[t][1]]);
}
}
int main(){
int n,m;
cin>>n>>m;
int now = 0,x;
int e = 0;
for(int i = 0;i < n;i ++){
scanf("%d",&x);
root[i + 1] = ++ ctx;
insert(24,x ^ now,root[i + 1],root[i],i + 1);
now ^= x;
s[i + 1] = now;
e = x;
}
char t;
int l,r;
int c = 1;
for(int i = 0;i < m; i++){
scanf(" %c",&t);
if(t == 'A'){
scanf("%d",&x);
root[n + c] = ++ ctx;
insert(24,now ^ x,root[n + c],root[n + c - 1],n + c);
now ^= x;
s[n + c] = now;
e = x;
c ++;
}
else {
scanf("%d %d %d",&l,&r,&x);
printf("%d\n",(query(l - 1,root[r - 1],now ^ x) ^ (now ^ x)));
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168600.html原文链接：https://javaforall.net
