「ALO」宝石融合问题题解

题目分析

这个问题要求我们找到一段连续的宝石区间，使得该区间的次大值与区间内其他任意宝石的异或值最大。

算法思路

核心观察

对于每个宝石 $a_i$，我们需要找到所有以 $a_i$ 作为次大值的区间，然后在对应的区间内找到与 $a_i$ 异或结果最大的值。

关键技术

1. 可持久化Trie树：用于快速查询区间内与给定值异或的最大值
2. 双向链表 + 排序：用于确定每个数作为次大值的支配区间
3. 离线处理：按数值从小到大处理，逐步删除已处理的数

代码解析

1. 可持久化Trie树实现

struct tree {
    int cnt, son[2];
} tr[31 * N];

void insert(int x) {
    rt[x] = ++cnt;
    int id1 = rt[x], id2 = rt[x - 1];
    
    for (int i = 29; i >= 0; i--) {
        int p = (a[x] >> i) & 1;
        tr[id1] = tr[id2], tr[id1].son[p] = ++cnt, tr[id1].cnt++;
        id1 = tr[id1].son[p], id2 = tr[id2].son[p];
    }
    tr[id1] = tr[id2], tr[id1].cnt++;
}

int query(int x, int id1, int id2) {
    int num = 0;
    for (int i = 29; i >= 0; i--) {
        int p = (x >> i) & 1;
        if (tr[tr[id1].son[p ^ 1]].cnt < tr[tr[id2].son[p ^ 1]].cnt) {
            id1 = tr[id1].son[p ^ 1], id2 = tr[id2].son[p ^ 1];
            num += (1 << i);
        } else {
            id1 = tr[id1].son[p], id2 = tr[id2].son[p];
        }
    }
    return num;
}

功能：

• insert(x)：构建第x个版本的可持久化Trie
• query(x, l, r)：在区间[l, r]中查询与x异或的最大值

2. 确定支配区间

// 按数值从小到大排序
sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; i++)
    pl[lower_bound(b + 1, b + 1 + n, a[i]) - b] = i;

// 初始化双向链表
for (int i = 1; i <= n; i++)
    l[i] = i - 1, r[i] = i + 1, tol[i] = tor[i] = -1;

// 从小到大处理每个数，确定其作为次大值的区间
for (int i = 1; i <= n; i++) {
    int x = pl[i];
    ls[x] = l[x], rs[x] = r[x];
    
    if (l[x]) tol[x] = l[l[x]];      // 左边第二个比它大的
    if (r[x] != n + 1) tor[x] = r[r[x]]; // 右边第二个比它大的
    
    r[l[x]] = r[x], l[r[x]] = l[x];  // 从链表中删除当前数
}

关键思路：

• 按数值从小到大处理，当前处理的数一定是当前剩余数中最小的
• 对于数 $a_x$，它作为次大值的区间必须包含比它大的两个数
• tol[x] 和 tor[x] 分别表示左右第二个比 $a_x$ 大的位置

3. 查询最大异或值

for (int i = 1; i <= n; i++) {
    if (~tol[i])  // 左边存在第二个更大的数
        ans = max(ans, query(a[i], rt[tol[i]], rt[rs[i] - 1]));
    
    if (~tor[i])  // 右边存在第二个更大的数  
        ans = max(ans, query(a[i], rt[ls[i]], rt[tor[i] - 1]));
}

两种情况：

1. 左边有两个更大的数：区间为 [tol[i]+1, rs[i]-1]
2. 右边有两个更大的数：区间为 [ls[i]+1, tor[i]-1]

算法复杂度

• 时间复杂度：$O(n \log A)$，其中 $A$ 是数值范围
• 空间复杂度：$O(n \log A)$

关键技巧

1. 离线处理：通过排序和链表确定每个数的支配区间
2. 可持久化数据结构：支持任意区间查询
3. 双向链表维护：高效找到每个数左右更大的数

总结

本题的巧妙之处在于将"次大值"的条件转化为对每个数支配区间的确定，然后利用可持久化Trie在对应区间内查询最大异或值。这种"确定支配区间 + 区间查询"的思路在很多问题中都有应用。