小优化

对y老师的insert函数做了下小的优化，我们只需在创建节点时，记录下树中节点所属元素的下标即可。

#include <iostream>
using namespace std;

const int N = 600010, M = N * 25; 

int tr[M][2], id[M]; //id保存树节点所属元素下标
int s[N]; //前缀异或和
int root[N];
int idx;
int n, m;

void insert(int i, int u, int p, int q) //p为前一版本的该位置点，q为后一个版本的该位置点
{
    if (u < 0) return;

    int v = s[i] >> u & 1;
    tr[q][v] = ++idx;
    id[idx] = i; //第i个数的所有节点，其id值为i

    if (p) tr[q][v ^ 1] = tr[p][v ^ 1]; //p存在，则复制前一版本节点
    insert(i, u - 1, tr[p][v], tr[q][v]); 
}

int query(int root, int l, int c)
{
    int p = root;
    for (int i = 23; i >= 0; i--)
    {
        int v = c >> i & 1;
        if (id[tr[p][v ^ 1]] >= l) p = tr[p][v ^ 1]; //优先往异或位位1的一侧查找
        else p = tr[p][v];
    }

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

int main()
{
    cin >> n >> m;

    id[0] = -1; //设置哨兵，插入元素时，无需特判
    root[0] = ++ idx;
    insert(0, 23, 0, root[0]);

    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);

        s[i] = s[i - 1] ^ x;
        root[i] = ++ idx; //先建立根节点
        insert(i, 23, root[i - 1], root[i]);
    }

    char op[2];
    int l, r, x;
    while (m -- )
    {
        scanf("%s", op);
        if (*op == 'A')
        {
            scanf("%d", &x);
            n ++ ;

            s[n] = s[n - 1] ^ x;
            root[n] = ++ idx; //先建立根节点
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            scanf("%d%d%d", &l, &r, &x); //卡cin
            printf("%d\n", query(root[r - 1], l - 1, s[n] ^ x)); //p属于[l,r]，异或和为s[p - 1]^c
        }
    }

    return 0;
}