题意

支持两个操作

  • A x:添加操作,表示在序列末尾添加一个数\(x\),序列的长度\(N+1\)。
  • Q l r x:询问操作,你需要找到一个位置\(p\),满足\(l\le p\le r\),使得:\(a[p]\; xor\; a[p+1]\; xor\; \cdots \; xor\; a[N]\; xor\; x\)最大,输出最大是多少。

分析

在区间\([l,r]\)中找一个\(p\)使得\(a[p]\; xor\; a[p+1]\; xor\; \cdots \; xor\; a[N]\; xor\; x\)最大。

我们记\(sum[x]=a[1]\; xor\; a[2]\; xor\; \cdots \; xor\; a[x]\),于是有\(a[p]\; xor\; a[p+1]\; xor\; \cdots \; xor\; a[N]\; xor\; x=sum[p-1]\; xor\; sum[n]\; xor \; x\)。

可以发现\(sum[n]\; xor \; x\)是常数,于是题目就变成了找一个\(p\),使得\(sum[p-1]\; xor \; const\)最大。即在区间\([l-1,r-1]\)中找一个\(p\)。

这个如果不规定区间的话,就是经典的字典树解决两数 xor 最大值的问题。

但是题目规定了区间,我们可以用类似于主席树的方法建立可持久化字典树。

用\(val[x]\)表示节点\(x\)中包含的单词个数,于是差分\(>0\)就表示这个区间有这个节点的单词,贪心得向反方向走即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注