天道酬勤,学无止境

Trle树

BZOJ 4260: Codechef REBXOR

Description Input输入数据的第一行包含一个整数N,表示数组中的元素个数。第二行包含N个整数A1,A2,…,AN。 Output输出一行包含给定表达式可能的最大值。 Sample Input51 2 3 1 2Sample Output6HINT 满足条件的(l1,r1,l2,r2)有:(1,2,3,3),(1,2,4,5),(3,3,4,5)。对于100%的数据,2 ≤ N ≤ 4*105,0 ≤ Ai ≤ 109。 Solution:  01trie树求异或和最大。  先正反都求一遍异或前缀和,每次都将当前的前缀和加入01tire树中,同时查询并更新$ln[i]$和$rn[i]$(分别表示$[1,i]$的最大连续异或和,$[i,n]$的最大连续异或和),那么答案$ans=max(ln[i]+rn[i+1])$,注意的细节是trie树要清0并在tire树中先插入一个0以便保证第一次插入的异或前缀和是其本身。代码: #include#define il inline#define ll long long#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)using namespace std;const int N

2021-05-18 16:03:58    分类:博客    Trle树   REBXOR