這個題目是USACO最后的一道題目，我在網上找了N多的題解，不是完全一樣的，就是說的不知道是什么東西的
不知道為啥，是不是所有搞OI的人在寫題解的時候都喜歡用“提示”的辦法，不直接把問題說清楚，而是隱隱約約的公訴你該怎么做，然后你讓你自己去想。
于是導致我到現在都沒有弄明白這道題目是怎么回事，盡管他們的做法有N多種，但是歸根到底都是在搞一個叫做前綴的東西。
下面這個是我在TopCoder上面找到的一個牛人的解釋，算是英語寫的比較好的，很通俗易懂的
上面這篇文章我想我就不用再翻譯了，說的比較清楚，但是他也沒有給出具體的算法，不過思路已經很清楚了
其實有了第一條性質之后，最樸素的辦法就是枚舉i和j，所以個2次循環，但是這樣顯然是要TLE的
在沒有更好的算法的前提下，這道題目的算法就是空間換時間，在我看來就是這樣的。
在看了N多代碼之后，我覺得還是USACO的Analysis的代碼看上去比較美，不知道為啥，那些用Hash和Trie的我都沒看懂，可能是我比較菜吧
下面我嘗試著把USACO的代碼解釋一下，看看能不能說清楚，很遺憾，由于這道題目的巨型的輸入數據，java肯定是沒辦法過的
1 int main() {
2 freopen("cowxor.in", "r", stdin);
3 freopen("cowxor.out", "w", stdout);
4 scanf("%i", &n);
5 xr[0] = 0;
6 for (a = 0; a < n; a++ ) {
7 scanf("%d", &x);
8 xr[a+1] = xr[a] ^ x;
9 }
10 for (a = 0; a <= n; a++ ) {
11 prev[a][0] = a-1;
12 prev[a][1] = -1;
13 best[a] = a-1;
14 }
15 wyk = 22;
16 res = 0;
17 while (wyk--) {
18 for (a = 1; a <= n; a++ )
19 if (prev[a][0] == -1)
20 prev[a][1] = -1;
21 else {
22 if (xr[a] >> wyk != xr[prev[a][0]] >> wyk) {
23 tmp[0] = prev[prev[a][0]][1];
24 tmp[1] = prev[a][0];
25 } else {
26 tmp[0] = prev[a][0];
27 tmp[1] = prev[prev[a][0]][1];
28 }
29 prev[a][0] = tmp[0];
30 prev[a][1] = tmp[1];
31 }
32 fnd = false;
33 for (a = 1; a <= n; a++ )
34 if (0 <= best[a])
35 if ((xr[a] >> wyk) % 2 != (xr[best[a]] >> wyk) % 2 ||
36 0 <= prev[best[a]][1])
37 fnd = true;
38 if (fnd) {
39 res |= 1 << wyk;
40 for (a = 1; a <= n; a++ )
41 if (0 <= best[a] &&
42 (xr[a] >> wyk) % 2 == (xr[best[a]] >> wyk) % 2)
43 best[a] = prev[best[a]][1];
44 }
45 }
46 for (a = 0; best[a] == -1; a++ );
47 printf("%d %d %d"n", res, best[a]+1, a);
48 return 0;
49 }
首先，6～9行，程序把從1開始到i位結束的所有的xor都求出來保存在了數組xor里面，我想這個就是為了方便后面用到xor的那個性質。
10～14行是一個 初始化的過程，這個prev的定義應該可以從USACO的Analysis上面看到：
xr[pop[q][0]]'s and xr[q]'s binary representations are the same on
positions e, e+1, etc., and pop[q][0] is biggest possible with 0 ≤
pop[q][0] < q. If there's no such pop[q][0] possible, then pop[q][0]
= -1.
xr[pop[q][1]]'s and xr[q]'s binary representations are the same on
positions e+2, e+2, etc., different on position e, and pop[q][1] is
biggest possible with 0 ≤ pop[q][1] < q. If there's no such
pop[q][1] possible, then pop[q][1] = -1.
我們要根據后面的循環來看這個prev數組的含義
外側的循環的作用是每次處理一位，由于題目中已經說明了，最多只有21位，所以循環21次就可以了。
我們來看內側的循環
18～31行，對所有的奶牛編號循環一遍，得到的結果就是：
對于當前的xor number，對于這個xor number的前21 - wyk位，與他相同的那個xor number的位置，并且，這個位置要盡量的靠后。
如果沒有相同的，那么這個位置就是-1
這樣，經過每次循環之后，prev里面就是與當前的xor number前k位相同的那個數的位置，一次一次循環，直到最后。
prev[i][0]存的是當current bit也相同的時候的位置，prev[i][1]存的是currnet bit不相同時候的位置，為什么要這樣呢？
這可能就需要解釋一下
if (xr[a] >> wyk != xr[prev[a][0]] >> wyk) {
tmp[0] = prev[prev[a][0]][1];
tmp[1] = prev[a][0];
} else {
tmp[0] = prev[a][0];
tmp[1] = prev[prev[a][0]][1];
}
如果當前比較的這一位相等，那么也就意味著prev[a][0]不用變，但是prev[i][1]卻必須變化，因為當前的這一位，已經不是剛才比較的那一位了，prev[a][1]應該等于此時的prev[a][0]的prev[a][1]，我想這個應該不難理解。
另一方面，如果當前比較的這一位不相等的時候，那么prev[a][1]就應該等于prev[a][0]了，因為之前的所有位都相等，之后當前這一位不相
等，這就是prev[a][1]的定義。那么prev[a][0]的值呢？我們需要注意的時候，當我們處理到a的時候，prev[a][0]位置的值肯定
是已經處理過的了。那么prev[a][prev[a][0]][1]里面存的就是與prev[a][0]在當前位不相等的那個xor
number的位置，注意，bit只有0和1，prev[a][0]與當前的不相等，而prev[a][prev[a][0]][1]又與prev[a]
[0]不相等，所以當前的prev[a][1]肯定與prev[a][prev[a][0]][1]是相等的。這就是 tmp[0] =
prev[prev[a][0]][1];的含義。
我再來看32～37行，首先要知道best[q]的定義：
if X would be equal biggest possible xor, then xr[best[q]] xor xr[q]'s
in equal X's binary representation on positions e, e+1, etc., and
best[q] is biggest possible with 0 ≤ best[q] < q. If there's no such
best[q] possible, then best[q] = -1.
想要得到盡量大的xor，那么就要盡量讓每一位都不相同 （xr[a] >> wyk) % 2就是取當前的二進制的最后一位
這段代碼的作用就是找，到當前位為止，是否有兩個xor number，他們的每一位都不相同，這樣就能保證異或結果是最大的。
接下來看38～45的這段代碼，因為我們是從高位到低位來處理的，這樣的話，如果能保證高位是1，那么比你所有的低位都是1都管用：）
于是，既然我們找到了高位是1的情況，那么我們就要記錄下結果 res
然后，剩下的那個循環就是更新best[a]
在所有的xor
number中，如果當前位跟best[a]的當前位是相等的，那么就更新best[a]，將其更新為prev[best[a]][1]，就是除了當前位
不相等，其余位不變的那個xor number，這樣就保證了從高位開始，每一位都能夠盡量取到1，因為只要高位盡量是1，我們的結果就能盡量的大。
其實prev這個數組里面真正有用的是prev[q][1]
不知道我解釋清楚了沒，其實解釋了一遍，自己也清楚了很多。