P4098 [HEOI2013]ALO 题解

· · 题解

  1. 一方面，次大值很棘手，最先考虑。
  2. 另一方面，对于一段区间内的 a_p(p\in[l,r])，如果要找它们和 k 异或起来的最大值是好找的。从最高位到最低位建 Trie，在树上贪心即可。因为是一段区间，需要可持久化 Trie。

不难想到枚举次大值，然后在 a_k 可作为次大值的区间内在可持久化 Trie 上找。

关于枚举次大值，可以见我的这篇题解。

记 \mathrm{minL} 和 \mathrm{maxR} 为 a_k 向左向右第一个比它大的 a_p 的 p。

可以考虑把这 n 个数用链表将相邻的两个数连在一起，然后从小到大枚举最大值，每次枚举完一个值，就把这个值删去，更新链表。

这样每个数在链表上的左右的数就是第一个大于它的值了，因为比它小都删掉了，换句话说它们直接确定了 \mathrm{minL}-1 和 \mathrm{maxR}+1。

// Problem: P4098 [HEOI2013]ALO
// From: Luogu
// URL: https://www.luogu.com.cn/problem/P4098
// Time: 2022-06-30 17:01
// Author: lingfunny

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 5.5e4+10, mxd = 30;

int n, a[mxn], rt[mxn], sz[mxn*mxd], ch[2][mxn*mxd], tot, b[mxn], L[mxn], R[mxn], ans;

void ins(int o, int &u, const int& w, int d = mxd - 1) {
    if(!u) u = ++tot;
    if(d < 0) return ++sz[u], void();
    const int f = (w >> d) & 1;
    ins(ch[f][o], ch[f][u], w, d - 1);
    ch[f^1][u] = ch[f^1][o];
    sz[u] = sz[ch[0][u]] + sz[ch[1][u]];
}

int ask(int l, int r, const int& w, int d = mxd - 1) {
    if(d < 0) return 0;
    const int f = ((w >> d) & 1) ^ 1;
    return sz[ch[f][r]] > sz[ch[f][l]] ? ask(ch[f][l], ch[f][r], w, d - 1) | (1 << d) : ask(ch[f^1][l], ch[f^1][r], w, d - 1);
}

signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", a+i), ins(rt[i-1], rt[i], a[i]),
    b[i] = i, L[i] = i - 1, R[i] = i + 1; R[n+1] = n + 1;
    sort(b+1, b+n+1, [&](int x, int y) { return a[x] < a[y]; });
    for(int i = 1; i < n; ++i) {
        int l = L[b[i]], r = R[b[i]];
        R[l] = r, L[r] = l;
        ans = max(ans, ask(rt[L[l]], rt[r-1], a[b[i]]));
        ans = max(ans, ask(rt[l], rt[R[r]-1], a[b[i]]));
    }
    printf("%d\n", ans);
    return 0;
}