Home => ProblemSet => 4.1-21:最大异或和
Problem2142--4.1-21:最大异或和

2142: 4.1-21:最大异或和

Time Limit: 2 Sec  Memory Limit: 512 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

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

Input

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

Output

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

Sample Input Copy 

5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4
Q 5 7 0 
Q 3 6 6

Sample Output Copy 

4
5
6

HINT

  • 对于所有测试点， 1≤N,M≤3×105，0≤ai≤107。

Source/Category

数据结构 Trie 
[ Submit ] [ Status ]