題目

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。

輸出格式

輸出一行一個整數，表示最大能生成的寶石能量密度。

輸入樣例

5

9 2 1 4 7

輸出樣例

14

提示

【樣例解釋】

選擇區間[1,5]，最大值為 7 xor 9。

對于 100%的數據有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9

題解

我們枚舉那個次大值的位置，然后我們找的可操作區間肯定是越大越好
然后用二分 + ST表找出最大的區間使得它為這個區間的最大值
要成為次大值，就跨過其中一個區間端點即可

然后就可以在可持久化trie樹上詢問答案了

注意區間邊界的處理細節

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 50005,B = 30,maxm = 100005,INF = 1000000000;
inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag;
}
int n,Log[maxn],bin[40],A[maxn],mx[maxn][17];
struct trie{int ch[maxn * 35][2],sum[maxn * 35],rt[maxn],cnt;int ins(int r,int x){int tmp,u;tmp = u = ++cnt;for (int i = B; i >= 0; i--){ch[u][0] = ch[r][0];ch[u][1] = ch[r][1];sum[u] = sum[r] + 1;int t = x & bin[i]; t >>= i;r = ch[r][t];u = ch[u][t] = ++cnt;}sum[u] = sum[r] + 1;return tmp;}int query(int u,int v,int x,int dep){if (dep < 0) return 0;LL t = x & bin[dep]; t >>= dep;if (sum[ch[u][t ^ 1]] - sum[ch[v][t ^ 1]])return bin[dep] + query(ch[u][t ^ 1],ch[v][t ^ 1],x,dep - 1);return query(ch[u][t],ch[v][t],x,dep - 1);}
}T;
int getmx(int l,int r){int t = Log[r - l + 1];return max(mx[l][t],mx[r - bin[t] + 1][t]);
}
void init(){bin[0] = 1; REP(i,35) bin[i] = bin[i - 1] << 1;Log[0] = -1; for (int i = 1; i < maxn; i++) Log[i] = Log[i >> 1] + 1;n = read();REP(i,n){mx[i][0] = A[i] = read();T.rt[i] = T.ins(T.rt[i - 1],A[i]);}REP(j,16) REP(i,n){if (i + bin[j] - 1 > n) break;mx[i][j] = max(mx[i][j - 1],mx[i + bin[j - 1]][j - 1]);}
}
void solve(){int l,r,mid,L,R,ans = 0;for (int i = 1; i <= n; i++){if (i == 1 || A[i - 1] >= A[i]) L = i;else {l = 0; r = i - 1;while (l < r){mid = l + r + 1 >> 1;if (getmx(i - mid,i - 1) < A[i]) l = mid;else r = mid - 1;}L = i - l;}if (i == n || A[i + 1] >= A[i]) R = i;else {l = 0; r = n - i;while (l < r){mid = l + r + 1 >> 1;if (getmx(i + 1,i + mid) < A[i]) l = mid;else r = mid - 1;}R = i + l;}if (L == 1 && R == n) continue;if (R < n){int tmp = R;R++;if (R == n || A[R + 1] >= A[i]) l = 0;else {l = 0; r = n - R;while (l < r){mid = l + r + 1 >> 1;if (getmx(R + 1,R + mid) < A[i]) l = mid;else r = mid - 1;}R += l;}if (L < R) ans = max(ans,T.query(T.rt[R],T.rt[L - 1],A[i],B));R = tmp;}if (L > 1){L--;if (L == 1 || A[L - 1] >= A[i]) l = 0;else {l = 0; r = L - 1;while (l < r){mid = l + r + 1 >> 1;if (getmx(L - mid,L - 1) < A[i]) l = mid;else r = mid - 1;}L -= l;}if (L < R) ans = max(ans,T.query(T.rt[R],T.rt[L - 1],A[i],B));}}printf("%d\n",ans);
}
int main(){init();solve();return 0;
}

轉載于:https://www.cnblogs.com/Mychael/p/8946423.html

總結

以上是生活随笔為你收集整理的BZOJ3166 [Heoi2013]Alo 【可持久化trie树 + 二分 + ST表】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。