首页 > 代码库 > BZOJ3261: 最大异或和
BZOJ3261: 最大异或和
3261: 最大异或和
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 543 Solved: 237
[Submit][Status]
Description
给定一个非负整数序列 {a}，初始长度为 N。
有 M个操作，有以下两种操作类型：
1 、A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N+1。
2 、Q l r x：询问操作，你需要找到一个位置 p，满足 l<=p<=r，使得：
a[p] xor a[p+1] xor ... xor a[N] xor x 最大，输出最大是多少。
Input
第一行包含两个整数 N ，M，含义如问题描述所示。
第二行包含 N个非负整数，表示初始的序列 A 。
接下来 M行，每行描述一个操作，格式如题面所述。
Output
假设询问操作有 T个，则输出应该有 T行，每行一个整数表示询问的答案。
Sample Input
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
对于测试点 1-2，N,M<=5 。
对于测试点 3-7，N,M<=80000 。
对于测试点 8-10，N,M<=300000 。
其中测试点 1, 3, 5, 7, 9保证没有修改操作。
对于 100% 的数据， 0<=a[i]<=10^7。
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
对于测试点 1-2，N,M<=5 。
对于测试点 3-7，N,M<=80000 。
对于测试点 8-10，N,M<=300000 。
其中测试点 1, 3, 5, 7, 9保证没有修改操作。
对于 100% 的数据， 0<=a[i]<=10^7。
Sample Output
4
5
6
5
6
HINT
对于 100% 的数据， 0<=a[i]<=10^7 。
题解：
神奇的可持久化trie！
把前缀和和x异或之后到l-1-r-1的trie树中查询即可。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1000000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,tot,rt[maxn],id[maxm],t[maxm][2]; 61 inline void insert(int pre,int x,int k) 62 { 63 int now=rt[k]=++tot;id[tot]=k; 64 for3(i,30,0) 65 { 66 int j=(x>>i)&1; 67 t[now][j^1]=t[pre][j^1]; 68 t[now][j]=++tot;id[tot]=k;now=tot; 69 pre=t[pre][j]; 70 } 71 } 72 inline int query(int l,int r,int x) 73 { 74 int ans=0,now=rt[r]; 75 for3(i,30,0) 76 { 77 int j=((x>>i)&1)^1; 78 if(id[t[now][j]]>=l)ans|=1<<i;else j^=1; 79 now=t[now][j]; 80 } 81 return ans; 82 } 83 84 int main() 85 86 { 87 88 freopen("input.txt","r",stdin); 89 90 freopen("output.txt","w",stdout); 91 92 n=read();m=read();int sum=0; 93 id[0]=-1; 94 insert(rt[0],0,0); 95 for1(i,n) 96 { 97 sum^=read(); 98 insert(rt[i-1],sum,i); 99 }100 while(m--)101 {102 char ch=getchar();103 while(ch!=‘A‘&&ch!=‘Q‘)ch=getchar();104 if(ch==‘A‘){sum^=read();insert(rt[n],sum,n+1);n++;}105 else106 {107 int l=read(),r=read(),x=read();108 printf("%d\n",query(l-1,r-1,sum^x));109 }110 }111 112 return 0;113 114 }
BZOJ3261: 最大异或和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。