P4098 ALO
题意
给定一个长度为 \(n\) 的互不相同的整数序列 \(a\)，定义一个区间 \([l,r]\) 的权值为 \(a_{l\sim r}\) 中的次大值 \(k\) 与 \(a_{l\sim r}\) 中任意一个数的异或值的最大值，即 \(\max\limits_{l\leqslant i\leqslant r} \{a_i\oplus k \}\)。
问所有区间权值的最大值。
数据范围
- \(1\leqslant n \leqslant 5\times 10^4\)。
- \(0\leqslant a_i \leqslant 10^9\)。
思路
假如我选择枚举最大值，那么次大值的位置似乎可以有很多，疑似需要使用单调栈，而且非常复杂，于是考虑枚举次大值。
一个数 \(a_i\) 能成为次大值，当且仅当区间内存在恰好一个数大于 \(a_i\)，也就是在 \(i\) 左右分别找到第一个大于其的位置 \(l,r\)，以 \(a_i\) 做次大值的区间即从 \([l,i]\) 和 \([i,r]\) 开始往外扩展。
那么它最多扩展至哪呢？不难发现扩展的途中不能出现任何一个位置 \(j\) 满足 \(a_j>a_i\)，对于 \([l,i]\)，其右端点最多也就是扩展至 \(r-1\)，而其左端点呢？不难想到再从 \(l-1\) 开始寻找下一个大于 \(a_i\) 的位置 \(l'\)，最终区间也就是 \([l'+1,r-1]\)。\([i,r]\) 也是同理。
从某个位置开始向左向右寻找第一个大于某个值的位置，可以使用预处理+倍增快速解决。
接下来就是问 \([l'+1,r-1]\) 和 \([l+1,r'-1]\) 中的值与 \(a_i\) 的异或值的最大值，非常经典，使用可持久化 01 字典树解决即可，可以参考 P4735 最大异或和。
要小心边界问题，即某个数左边或右边可能没有比他大的数，那么这种情况下他无法成为次大值。
复杂度
- 时间：\(O(n\log V)\)。
- 空间：\(O(n\log V)\)。
Code
点击查看代码
#include <iostream>
#define _1 (__int128)1using namespace std;
using ll = long long;
using pii = pair<int, int>;void FileIO (const string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);
}const int N = 5e4 + 10, INF = 1e9 + 10;int n, a[N], pre[16][N], suf[16][N], trie[N << 5][2], sum[N << 5], tid, rt[N], ans;int GetPre (int x, int t) {if (x < 1) return 0;for (int i = 15; i >= 0; i--)if (pre[i][x] <= t)x -= (1 << i);return x;
}int GetSuf (int x, int t) {if (x > n) return n + 1;for (int i = 15; i >= 0; i--)if (suf[i][x] <= t)x += (1 << i);return x;
}void Insert (int x, int y) {rt[x] = ++tid;for (int i = 29, now = rt[x], lst = rt[y]; i >= 0; i--) {int t = (a[x] >> i & 1);trie[now][!t] = trie[lst][!t], trie[now][t] = ++tid, now = tid, lst = trie[lst][t];sum[now] = sum[lst] + 1;}
}int Query (int l, int r, int y) {int ret = 0;for (int i = 29, now = rt[r], lst = rt[l - 1]; i >= 0; i--) {int t = (y >> i & 1);if (sum[trie[now][!t]] != sum[trie[lst][!t]]) now = trie[now][!t], lst = trie[lst][!t], ret += (1 << i);else now = trie[now][t], lst = trie[lst][t];}return ret;
}signed main () {ios::sync_with_stdio(0), cin.tie(0);// FileIO("");cin >> n, pre[0][0] = suf[0][n + 1] = INF, rt[0] = ++tid;for (int i = 1; i <= n; i++) cin >> a[i], pre[0][i] = suf[0][i] = a[i], Insert(i, i - 1);for (int i = 1; i <= 15; i++)for (int j = 0; j <= n + 1; j++)pre[i][j] = max(pre[i - 1][j], pre[i - 1][max(0, j - (1 << (i - 1)))]), suf[i][j] = max(suf[i - 1][j], suf[i - 1][min(n + 1, j + (1 << (i - 1)))]);for (int i = 1; i <= n; i++) {int l = GetPre(i, a[i]), r = GetSuf(i, a[i]);int l_ = GetPre(l - 1, a[i]), r_ = GetSuf(r + 1, a[i]);if (l > 0) ans = max(ans, Query(l_ + 1, r - 1, a[i]));if (r <= n) ans = max(ans, Query(l + 1, r_ - 1, a[i]));}cout << ans;return 0;
}