Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

12/11
12:42
trie

[bzoj 4260] Codechef REBXOR

♦♦♦♦♦♦   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*105,0 ≤ Ai ≤ 109。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

做一遍前缀和,就是要求出max(s[l1]^s[r1]+s[l2]^s[r2])(0<=l1<r1<=l2<r2<=n)

从左往右用trie树求出lm[i]表示当前最大的s[l1]^s[r1],然后同理从右往左做一遍求出rm[i]

之后瞎搞一下

 

[bzoj 4260] Codechef REBXOR