异或和左移的优先级_异或链表

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

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)));
}
}
}