BZOJ 3166 「HEOI2013」ALO

一个非常傻的做法是，枚举区间，使用 ST 表求得次大值并 Trie 算答案。
但是这样真的非常傻……

考虑到每个区间的次大值只有一个，我们可以枚举这个次大值，并找次大值为它的区间。
具体地说，把 ai 降序，然后用 set 维护。

不过这个做法是有问题的，比如这组数据：

3
12 1 4

输出应该是 8(12⊕4)，但我的代码输出 13(12⊕1)。
不过数据太水了……

代码：

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
const int N = 5e4;
const int LG = 30;
int n,a[N + 5],b[N + 5],ans;
set<int> d;
inline bool cmp(int x,int y)
{
    return a[x] > a[y];
}
struct node
{
    int sum;
    int ch[2];
} trie[(N << 7) + 10];
int rt[N + 5];
void insert(int v,int &p)
{
    static int tot = 0;
    trie[++tot] = trie[p],++trie[p = tot].sum;
    int cur = p;
    for(register int i = LG;i;--i)
    {
        trie[++tot] = trie[trie[cur].ch[(v >> i - 1) & 1]],trie[cur].ch[(v >> i - 1) & 1] = tot;
        cur = trie[cur].ch[(v >> i - 1) & 1],++trie[cur].sum;
    }
}
int query(int v,int p,int q)
{
    int ret = 0;
    for(register int i = LG;i;--i)
        if(trie[trie[q].ch[((v >> i - 1) & 1) ^ 1]].sum - trie[trie[p].ch[((v >> i - 1) & 1) ^ 1]].sum)
            ret += 1 << i - 1,p = trie[p].ch[((v >> i - 1) & 1) ^ 1],q = trie[q].ch[((v >> i - 1) & 1) ^ 1];
        else
            p = trie[p].ch[(v >> i - 1) & 1],q = trie[q].ch[(v >> i - 1) & 1];
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),b[i] = i,insert(a[i],rt[i] = rt[i - 1]);
    sort(b + 1,b + n + 1,cmp);
    d.insert(-1),d.insert(0),d.insert(b[1]),d.insert(n + 1),d.insert(n + 2);
    for(register int i = 2,l,r;i <= n;d.insert(b[i++]))
    {
        l = max(1,*----d.lower_bound(b[i]) + 1),r = min(n,*++d.upper_bound(b[i]) - 1);
        l <= r && (ans = max(ans,query(a[b[i]],rt[l - 1],rt[r])));
    }
    printf("%d\n",ans);
}