题目描述
可持续化:每个版本只和前一个版本比较
左子树中是否至少存在一个数的下标>=L <=> 左子树的下标最大值>=l
前缀和:转化成最大异或对问题
可持久化:处理右边限制
maxid:同时左右两边限制
注意query函数,这样写是可以过的
int query(int pos, int num, int l) {
int p = pos;
for(int i = 23; i >= 0; i--) {
int id = (num >> i) & 1;
if(max_id[tr[p][id ^ 1]] >= l) p = tr[p][id ^ 1];
else p = tr[p][id];
}
return num ^ s[max_id[p]];
}
这样写过不了
int query(int p, int c, int l)
{
for(int i = 23; i >= 0; i --)
{
int v = c >> i & 1;
if(max_id[tr[p][v ^ 1]] >= l)p = tr[p][v ^ 1];
else p = tr[p][v];
}
return c ^ s[max_id[p]];
}
#include <iostream>
#include <cstring>
using namespace std;
const int N=600010,M=N*25;
int n,m;
//01串,只有两种节点
int tr[M][2],max_id[M];
int s[N],root[N],idx;
//p为当前版本,q为上一版本,i为前缀和下标。k为当前处理到第几位
void insert(int i,int k,int p,int q)
{
//如果k小于0则说明处理到最后一位
if(k<0)
{
max_id[q]=i;
return;
}
//v存当前这一位
int v=s[i]>>k&1;
//另外一位要存q的复制
if(p) tr[q][v^1]=tr[p][v^1];
tr[q][v]=++idx;
insert(i,k-1,tr[p][v],tr[q][v]);
max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
}
int query(int pos, int num, int l) {
int p = pos;
for(int i = 23; i >= 0; i--) {
int id = (num >> i) & 1;
if(max_id[tr[p][id ^ 1]] >= l) p = tr[p][id ^ 1];
else p = tr[p][id];
}
return num ^ s[max_id[p]];
}
int main()
{
scanf("%d%d", &n, &m);
s[0] = 0;
max_id[0] = -1;
root[0] = ++ idx;
insert(0,23,0,root[0]);
for(int i = 1; i <= n; i ++)
{
int x;
scanf("%d", &x);
root[i] = ++ idx;
s[i] = s[i - 1] ^ x;
insert(i,23,root[i-1],root[i]);
}
while(m --)
{
char op[2];
scanf("%s", op);
if(*op == 'A')
{
int x;
scanf("%d", &x);
n ++;
root[n] = ++ idx;
s[n] = s[n - 1] ^ x;
insert(n,23,root[n-1],root[n]);
}
else
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(root[r-1],s[n]^x,l-1));
}
}
return 0;
}