给定一个非负整数序列 {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行，每行一个整数表示询问的答案。

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

 1 #include <cstdio> 2  3 const int mxn = 1E6; 4 const int siz = 2E7; 5  6 int n, m; 7   8 int a[mxn]; 9 int b[mxn];10 11 int tot;12 int rt[mxn];13 int ls[siz];14 int rs[siz];15 int sm[siz];16 17 void insert(int &t, int p, int c, int d)18 {19     t = ++tot;20     21     ls[t] = ls[p];22     rs[t] = rs[p];23     sm[t] = sm[p] + 1;24     25     if (c < 0)return;26     27     if ((d >> c) & 1)28         insert(rs[t], rs[p], c - 1, d);29     else30         insert(ls[t], ls[p], c - 1, d);31 }32 33 int query(int a, int b, int c, int d)34 {35     if (c < 0)return 0;36     37     int bit = (d >> c) & 1;38     39     if (bit)40     {41         if (sm[ls[a]] - sm[ls[b]])42             return query(ls[a], ls[b], c - 1, d) | (1 << c);43         else44             return query(rs[a], rs[b], c - 1, d);45     }46     else47     {48         if (sm[rs[a]] - sm[rs[b]])49             return query(rs[a], rs[b], c - 1, d) | (1 << c);50         else51             return query(ls[a], ls[b], c - 1, d);52     }53 }54 55 signed main(void)56 {57     scanf("%d%d", &n, &m); ++n;58     59     for (int i = 2; i <= n; ++i)60         scanf("%d", a + i);61     62     for (int i = 1; i <= n; ++i)63         b[i] = b[i - 1] ^ a[i];64     65     for (int i = 1; i <= n; ++i)66         insert(rt[i], rt[i - 1], 25, b[i]);67     68     for (int i = 1; i <= m; ++i)69     {70         static char s[5];71         72         scanf("%s", s);73         74         if (s[0] == ‘A‘)75         {76             scanf("%d", a + ++n);77             b[n] = b[n - 1] ^ a[n];78             insert(rt[n], rt[n - 1], 25, b[n]);79         }80         else81         {82             int l, r, k;83             scanf("%d%d%d", &l, &r, &k);84             printf("%d\n", query(rt[r], rt[l - 1], 25, k ^ b[n]));85         }86     }87 }