题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3261
题意：对于一个初始长度为 n 的序列 a，维护 m 个操作，为下两种之一：
A x ：添加操作：表示在序列末尾添加一个数 x
Q l r x：询问操作：找到一个位置 p，满足 \(l\leq p\leq r\) 且使得：\(a_p\oplus a_{p+1}...\oplus a_{n}\oplus x\) 最大，输出最大值。
约定
二元组 (l,r) 表示从\(a_l\) 到\(a_r\) 的连续异或值
为了做 3261 得先会做 3689 ...
现在我们考虑这道题，在数列后面加数还要查询区间最大后缀异或值，是不好搞的... 所以有一个重要的思想是转换成前缀查询：
我们知道异或是满足结合律的，且 a^a=0，那么 (l,r)=(1,l-1)^(1,r)，大概就是把 (1,r) 的前一部分提出来即可
所以我们可以只维护前缀异或值，记为 sum，每次查询实际上为找到一个满足条件的 p 使得 x^sumn^sump 最大
如果没有区间限制，询问是在整个序列上的，建立 trie 树贪心即可，同 3689，但是有区间限制，所以每次我们需要单独考虑区间中的数
可持久化即可。每次在 tire 树上贪心，每棵树维护 size，通过 l-1 和 r 两棵树区间减查询即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iomanip> #include <iostream> #include <algorithm> #define N 600010 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,a[N],b[N]; int ch[N*24][2],tot,root[N],sz[N*24]; int add(int x,int v) { int now=++tot,tmp=now; for(int i=23;i>=0;i--) { ch[now][0]=ch[x][0],ch[now][1]=ch[x][1]; sz[now]=sz[x]+1; bool p=v&(1<<i); ch[now][p]=++tot; x=ch[x][p],now=ch[now][p]; } sz[now]=sz[x]+1; return tmp; } int ask(int l,int r,int v) { int now=0; for(int i=23;i>=0;i--) { bool p=v&(1<<i); if(sz[ch[r][p^1]]-sz[ch[l][p^1]]) now+=(1<<i),l=ch[l][p^1],r=ch[r][p^1]; else l=ch[l][p],r=ch[r][p]; } return now; } char opt[5]; int l,r,x; int main() { n=read()+1,m=read(); for(int i=2;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=b[i-1]^a[i]; for(int i=1;i<=n;i++)root[i]=add(root[i-1],b[i]); while(m--) { scanf("%s",opt); if(opt[0]=='A') { a[++n]=read(),b[n]=b[n-1]^a[n]; root[n]=add(root[n-1],b[n]); } else { l=read(),r=read(),x=read(); printf("%d\n",ask(root[l-1],root[r],b[n]^x)); } } } |
Comments | NOTHING