题目概述

有 $m$ 个操作：1.在末尾添加一个数 $a_{n+1}$ 。2.询问 $max\{a_p\ xor\ a_{p+1}\ xor\ \cdots\ xor\ a_n\ xor\ x|l\le p\le r\}$ 。

解题报告

我竟然没做过这题……题目要求 $max\{sum_{n}\ xor\ sum_{p-1}\ xor\ x|l\le p\le r\}$ ，我们把 $sum_n\ xor\ x$ 扔进 $[l,r]$ 的Trie里询问就行了，Trie可持久化一下。

示例程序

没return now;然后WA了几发……

#include<cstdio>
using namespace std;
const int maxn=600000,Log=25,maxt=maxn*Log;

int n,m,s[Log],sum[maxn+5],ro[maxn+5],si,son[maxt+5][2],num[maxt+5];

int Insert(int p,int x=Log-1){
    int now=++si;num[now]=num[p]+1;son[now][0]=son[p][0];son[now][1]=son[p][1];if (x<0) return now;
    if (s[x]) son[now][1]=Insert(son[p][1],x-1); else son[now][0]=Insert(son[p][0],x-1);return now;
}
inline void reads(int x) {for (int i=0;i<24;i++) s[i]=x>>i&1;}
inline void Add(int x) {sum[++n]=x;sum[n]^=sum[n-1];reads(sum[n]);ro[n]=Insert(ro[n-1]);}
int Ask(int A,int B,int x=Log-1){
    if (x<0) return 0;int d=num[son[A][s[x]^1]]<num[son[B][s[x]^1]];
    return Ask(son[A][s[x]^d],son[B][s[x]^d],x-1)+(d<<x);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    int N;scanf("%d%d",&N,&m);ro[0]=si=1;Add(0);for (int i=1,x;i<=N;i++) scanf("%d",&x),Add(x);
    for (char tp;m;m--){
        int x,y,z;tp=getchar();while (tp!='A'&&tp!='Q') tp=getchar();scanf("%d",&x);
        if (tp=='A') Add(x); else scanf("%d%d",&y,&z),reads(z^sum[n]),printf("%d\n",Ask(ro[x-1],ro[y]));
    }return 0;
}