Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ，
如名字所见，到处充满了数学的谜题。
现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量
密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai, ai+1, …, a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值
与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次大值
为k，则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。
现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。
第一行，一个整数 n，表示宝石个数。
第二行， n个整数，分别表示a1至an，表示每颗宝石的能量密度，保证对于i ≠ j有 ai ≠ aj。
输出一行一个整数，表示最大能生成的宝石能量密度。
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
首先，应该枚举选择哪个数字作为次大值，然后需要知道其对应的可以选取哪个范围内的数字作为题目中的$ap$。
范围可以通过预处理得到，方法是先用二分得到每个数左侧第一个大于这个数的地方，然后再二分出第二个大于这个数的地方。每个数到两侧第二个大于这个数的范围就是$ap$的可选范围，不含第二个大于这个数的数字。
然后，问题转化为求一个数字在一个区间内的最大异或数字，这个问题是经典的Trie树问题，尽量“反着跑”即可。但是有区间限制，并且是n组询问，所以可以用大佬的可持久化Trie或我这种蒟蒻的莫队+Trie解决。
1 #include <bits/stdc++.h> 2 3 const int siz = 50005; 4 5 int n, num[siz]; 6 7 int st_maxi[siz][17]; 8 9 inline void preworkST(void) 10 { 11 for (int i = 1; i <= n; ++i) 12 st_maxi[i][0] = num[i]; 13 14 for (int i = 1; i < 17; ++i) 15 for (int j = 1; j <= n; ++j) 16 if (j + (1 << i) - 1 <= n) 17 st_maxi[j][i] = std::max( 18 st_maxi[j][i - 1], 19 st_maxi[j + (1 << (i - 1))][i - 1]); 20 } 21 22 inline int stMax(int l, int r) 23 { 24 if (l > r)return -1; 25 26 int len = r - l + 1, log = 0; 27 28 while (len >= (1 << (log + 1)))++log; 29 30 return std::max( 31 st_maxi[l][log], 32 st_maxi[r - (1 << log) + 1][log]); 33 } 34 35 int nt_pre[siz]; 36 int nt_nxt[siz]; 37 38 inline void preworkNT(void) 39 { 40 for (int i = 1; i <= n; ++i) 41 { 42 int val = num[i], lt = 1, rt = i, mid, pos = 1, ans = 1; 43 44 while (lt <= rt) 45 { 46 mid = (lt + rt) >> 1; 47 48 if (stMax(mid, i) > val) 49 lt = mid + 1, pos = mid; 50 else 51 rt = mid - 1; 52 } 53 54 lt = 1, rt = pos - 1; 55 56 while (lt <= rt) 57 { 58 mid = (lt + rt) >> 1; 59 60 if (stMax(mid, pos - 1) > val) 61 lt = mid + 1, ans = mid; 62 else 63 rt = mid - 1; 64 } 65 66 nt_pre[i] = ans; 67 } 68 69 for (int i = 1; i <= n; ++i) 70 { 71 int val = num[i], lt = i, rt = n, mid, pos = n, ans = n; 72 73 while (lt <= rt) 74 { 75 mid = (lt + rt) >> 1; 76 77 if (stMax(i, mid) > val) 78 rt = mid - 1, pos = mid; 79 else 80 lt = mid + 1; 81 } 82 83 lt = pos + 1, rt = n; 84 85 while (lt <= rt) 86 { 87 mid = (lt + rt) >> 1; 88 89 if (stMax(pos + 1, mid) > val) 90 rt = mid - 1, ans = mid; 91 else 92 lt = mid + 1; 93 } 94 95 nt_nxt[i] = ans; 96 } 97 } 98 99 struct query { 100 int l, r, t, ans; 101 }q[siz]; 102 103 int s; 104 105 inline bool cmp(const query &a, const query &b) 106 { 107 if (a.l / s != b.l / s) 108 return a.l < b.l; 109 else 110 return a.r < b.r; 111 } 112 113 const int tri = 5000005; 114 115 int next[tri][2], sum[tri], tot = 1; 116 117 inline void insert(int t) 118 { 119 int p = 1; 120 121 for (int i = 30; i >= 0; --i) 122 { 123 int c = (t >> i) & 1; 124 125 if (!next[p][c]) 126 next[p][c] = ++tot; 127 128 p = next[p][c]; 129 130 ++sum[p]; 131 } 132 } 133 134 inline void remove(int t) 135 { 136 int p = 1; 137 138 for (int i = 30; i >= 0; --i) 139 { 140 int c = (t >> i) & 1; 141 142 if (!next[p][c]) 143 next[p][c] = ++tot; 144 145 p = next[p][c]; 146 147 --sum[p]; 148 } 149 } 150 151 inline int query(int t) 152 { 153 int ret = 0, p = 1; 154 155 for (int i = 30; i >= 0; --i) 156 { 157 int c = (t >> i) & 1; 158 159 if (sum[next[p][c^1]]) 160 p = next[p][c^1], ret |= (1 << i); 161 else if (sum[next[p][c]]) 162 p = next[p][c]; 163 else 164 return 0; 165 } 166 167 return ret; 168 } 169 170 signed main(void) 171 { 172 scanf("%d", &n); 173 174 for (int i = 1; i <= n; ++i) 175 scanf("%d", num + i); 176 177 preworkST(); 178 179 preworkNT(); 180 181 for (int i = 1; i <= n; ++i) 182 { 183 q[i].l = nt_pre[i]; 184 q[i].r = nt_nxt[i]; 185 q[i].t = num[i]; 186 q[i].ans = 0; 187 } 188 189 s = sqrt(n); 190 191 std::sort(q + 1, q + 1 + n, cmp); 192 193 int lt = 1, rt = 0, maxi = stMax(1, n); 194 195 for (int i = 1; i <= n; ++i) 196 { 197 while (lt < q[i].l)remove(num[lt++]); 198 while (lt > q[i].l)insert(num[--lt]); 199 while (rt > q[i].r)remove(num[rt--]); 200 while (rt < q[i].r)insert(num[++rt]); 201 if (q[i].t != maxi)q[i].ans = query(q[i].t); 202 } 203 204 int answer = 0; 205 206 for (int i = 1; i <= n; ++i) 207 answer = std::max(answer, q[i].ans); 208 209 printf("%d\n", answer); 210 }
@Author: YouSiki
原文：http://www.cnblogs.com/yousiki/p/6274095.html