usaco training 6.1 牛異或 字首異或和+異或字典樹

題意

農夫約翰在給他的奶牛們喂食時遇到了一個問題。

他共有 N 頭奶牛，編号 1∼N。

每次喂食前，這 N 頭奶牛會按照 1∼N 的順序站成一排。

此外，每頭奶牛都被配置設定了一個可能不唯一的整數。

那麼所有被配置設定的整數就形成了一個長度為 N 的整數序列。

請你在該整數序列中找出一個連續的非空子序列，使得子序列中元素的異或和能夠最大。

如果存在多個這樣的序列，那麼選擇序列末端整數對應的奶牛編号更小的那個序列。

如果仍然存在多個可選的序列，那麼選擇長度最短的那個序列。

輸入格式

第一行包含整數 N。

第 2∼N+1 行，每行包含一個整數，其中第 i 行的整數表示編号為 i−1 的牛被配置設定的整數值。

輸出格式

輸出三個整數，分别表示最大的異或和，所選序列首端整數對應的奶牛編号，所選序列末端整數對應的奶牛編号。

資料範圍

1≤N≤105，

配置設定給奶牛的整數的範圍是 [0,221−1]。

輸入樣例：

5

1

4

2

輸出樣例：

6 4 5

題解

• 定義sum^=sum[i-1]，即字首異或和,則l-r的區間異或和sum[l~r] = sum[r] ^ sum[l-1]，題意轉為求sum數組中最大的異或對（兩個數）。
• 異或字典樹可以求某一個數和一組數中的最大異或對。
• 題目要求輸出長度最小的區間，并且右端點r也應該最小，固定求r，求前面的最大的j即可。