#3166. [Heoi2013]Alo

• description
• solution
• code

BZOJ3166

description

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}。
現在你需要知道你怎么選取需要融合的寶石，才能使生成的寶石能量密度最大。

Input

第一行，一個整數 n，表示寶石個數。
第二行， n個整數，分別表示a1至an，表示每顆寶石的能量密度，保證對于i ≠ j有 ai ≠ aj。

Output

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

Sample Input

5 9 2 1 4 7

Sample Output

14

Hint

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

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

solution

首先肯定是枚舉每一個寶石的$a_i$作為次大值

區間$[l,r]$內與$x$異或的最大值，就是可持久化trie樹

對于$i$版本的trie樹記錄的是$[1,i]$的所有寶石信息

但是本題的難點是在于求出每個寶石做次大值時，有效的區間范圍

定義前驅的含義：寶石密度大于$a_i$的在$i$前面的距$i$最近的寶石

定義后繼的含義：寶石密度大于$a_i$的在$i$后面的距$i$最近的寶石

對于每個$i$，詢問的合法區間其實是前驅的前驅位置l加一，后繼的后繼位置r減一

• 這里就有問題了，看似好像包含了兩個比$a_i$大的寶石，$i$寶石不再是次大值寶石

  • 其實并不是，要求包含前驅后繼并不是意味著在$(l,r)$這個區間進行詢問

    這個區間當然$i$寶石是次次大值

  • 這是意味著兩個獨立區間的問題$(l,i];[i,r)$

    這么說的原因是，假設$a_i?a_j(l<j<i<r)$是最大值，那么相當于選擇的區間是$(l,i]$。

    同理假設$a_i?a_j(l<i<j<r)$是最大值，那么相當于選擇的區間是$[i,r)$

    這樣$a_i$在兩個區間就扮演著次大值的角色了

  • 如果只是對于一個$i$考慮前驅的位置加一到后繼的后繼位置減一，其實只是考慮了最大值在次大值$a_i$后面的區間，忽略了最大值在$a_i$前面的區間

  • 如果只是對于一個$i$考慮前驅的前驅位置加一到后繼的位置減一，其實只是考慮了最大值在次大值$a_i$前面的區間，忽略了最大值在$a_i$后面的區間

知道了選取區間端點的條件，代碼怎么找呢？

• set

具體而言：將寶石按照密度排序，按密度從大到小地加入寶石，set里面放的是寶石的下標$i$，那么此時set里面的所有寶石都大于等于現在這個剛加進去的寶石密度

為了能闡釋得更清楚，我們直接解讀代碼

首先是尋找后繼的后繼的位置，減一會在主函數的查詢調用時減掉，這里暫時不考慮

• 這里兩個if語句的先后順序是先讓迭代器it自加后，再判斷是否指向了set的end()位置

• 眾所周知set是左閉右開的，end()位置是最后一個值的位置的下一個空位置

• 先自加一，指向后繼；再自加一，指向后繼的后繼

• int find_r( int x ) {auto it = s.find( x );if( ++ it == s.end() ) return n + 1;if( ++ it == s.end() ) return n + 1;return *it; }

然后看尋找前驅的前驅代碼，同樣的加一操作在主函數的詢問完成，這里不進行加一

• 這里兩個if語句的先后順序是，先判斷是否指向了begin()位置，再自減一

• 第一個if如果成立，意味著當前加入的寶石下標最小，前驅都沒有

• 否則，迭代器就指向了前驅

• 再到第二個if語句，如果成立，意味著前驅就是下標最小的寶石了，前驅的前驅沒有

• 否則迭代器就指向了前驅的前驅，達到目的

int find_l( int x ) {auto it = s.find( x );if( it -- == s.begin() ) return 0;if( it -- == s.begin() ) return 0;return *it; }

最后還有一個代碼細節

在插入操作和查詢操作中，涉及到最后一層二進制位$0$的處理

void insert( int &now, int lst, int x, int d ) {if( d < 0 ) return;t[now = ++ cnt] = t[lst];t[now].sum ++;int k = x >> d & 1;insert( t[now].son[k], t[lst].son[k], x, d - 1 ); }int query( int l, int r, int x, int d ) {if( t[r].sum - t[l].sum == 0 ) return 0;if( d == 0 ) return 1;int k = x >> d & 1;if( t[t[r].son[k ^ 1]].sum - t[t[l].son[k ^ 1]].sum )return query( t[l].son[k ^ 1], t[r].son[k ^ 1], x, d - 1 ) + ( 1 << d );elsereturn query( t[l].son[k], t[r].son[k], x, d - 1 ); }

如果不在query操作設置if( d == 0 ) return 1的這個出口，在insert的時候就必須把二進制位$?1$建出來，即

void insert( int &now, int lst, int x, int d ) {t[now = ++ cnt] = t[lst];t[now].sum ++;if( d < 0 ) return;int k = x >> d & 1;insert( t[now].son[k], t[lst].son[k], x, d - 1 ); }int query( int l, int r, int x, int d ) {if( d < 0 ) return 0;if( t[r].sum - t[l].sum == 0 ) return 0;int k = x >> d & 1;if( t[t[r].son[k ^ 1]].sum - t[t[l].son[k ^ 1]].sum )return query( t[l].son[k ^ 1], t[r].son[k ^ 1], x, d - 1 ) + ( 1 << d );elsereturn query( t[l].son[k], t[r].son[k], x, d - 1 ); }

為什么呢？

• 如果不在查詢時設置最底層葉子的出口，那么就會進入對葉子左右兒子的if判斷
• 然而，插入操作又只在最底層葉子建點后就返回了
• 所以葉子節點的兒子沒有被分配過，貿然訪問，完全不知道計算機會找到哪兒去
• 我就是這個順序細節問題，一直比答案少一

code

#include <set> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 50005 set < int > s; pair < int, int > a[maxn]; int n, cnt; int root[maxn]; struct { int son[2], sum; } t[maxn * 35];void insert( int &now, int lst, int x, int d ) {if( d < 0 ) return;t[now = ++ cnt] = t[lst];t[now].sum ++;int k = x >> d & 1;insert( t[now].son[k], t[lst].son[k], x, d - 1 ); }int query( int l, int r, int x, int d ) {if( t[r].sum - t[l].sum == 0 ) return 0;if( d == 0 ) return 1;int k = x >> d & 1;if( t[t[r].son[k ^ 1]].sum - t[t[l].son[k ^ 1]].sum )return query( t[l].son[k ^ 1], t[r].son[k ^ 1], x, d - 1 ) + ( 1 << d );elsereturn query( t[l].son[k], t[r].son[k], x, d - 1 ); }int find_l( int x ) {auto it = s.find( x );if( it -- == s.begin() ) return 0;if( it -- == s.begin() ) return 0;return *it; }int find_r( int x ) {auto it = s.find( x );if( ++ it == s.end() ) return n + 1;if( ++ it == s.end() ) return n + 1;return *it; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &a[i].first );a[i].second = i;insert( root[i], root[i - 1], a[i].first, 30 );}sort( a + 1, a + n + 1 );int ans = 0;s.insert( a[n].second );for( int i = n - 1;i;i -- ) {s.insert( a[i].second );int l = find_l( a[i].second );int r = find_r( a[i].second );ans = max( ans, query( root[l], root[r - 1], a[i].first, 30 ) );}printf( "%d\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的BZOJ #3166. [Heoi2013]Alo（可持久化trie树+set）的全部內容，希望文章能夠幫你解決所遇到的問題。

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