【BZOJ】4260:CodechefREBXOR【Trie树】【前后缀异或最大】

4260:CodechefREBXORTimeLimit:10SecMemoryLimit:256MBSubmit:2218Solved:962[Submit][Status][D

4260: Codechef REBXOR

Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 2218  Solved: 962[Submit][Status][Discuss]

Description

 

Input

输入数据的第一行包含一个整数N表示数组中的元素个数。 第二行包含N个整数A1,A2,…,AN。

 

Output

输出一行包含给定表达式可能的最大值。

 

Sample Input

5 1 2 3 1 2

Sample Output

6

HINT

 

满足条件的(l1,r1,l2,r2)有(1,2,3,3)(1,2,4,5)(3,3,4,5)。 对于100%的数据2 ≤ N ≤ 4*1050 ≤ Ai ≤ 109。

---

Solution

用trie树处理出以$i$结尾的最大区间异或前后分别扫一遍处理前缀和后缀。具体做法是将前缀或后缀插入trie树中每次用前缀或后缀在trie树中查询异或最大就是查询以$i$结尾的区间异或最大。

然后每个位置与前面取max最后合并统计答案即可。

Code

#includeusing namespace std;int n, a[400005], l[400005], r[400005];int son[31*400005][2], tail;void read(int 0; char ch getchar();while(ch > 9 || ch 0 9) {x x * 10 ch - 0;ch getchar();}}void insert(int x) {int nd 0;for(int i 30; ~i; i --) {int t 1 if(!son[nd][t]) son[nd][t] tail;nd son[nd][t];}}int query(int x) {int nd 0, ans 0;for(int i 30; ~i; i --) {int t 1 if(son[nd][!t]) {ans (1 < 1; i --) r[i] max(r[i], r[i 1]);long long ans 0;for(int i 1; i < n; i )ans max(ans, 1ll * (l[i] r[i 1]));printf("%lld", ans);return 0;}

 

转:https://www.cnblogs.com/wans-caesar-02111007/p/9834735.html