ACM模版

描述

题解

正反向单调递减栈搞一遍即可。

因为在单调递减栈的求解过程中，每一次 push 值时都保证 push 前的 top 值大于要 push 的值，并且中间所有的数小于要 push 的值和 push 前的 top 值，所以呢，这两个值刚刚是该区间的最大和次大值，异或求最即可，当然还要反向搞一下，依然是递减栈。

这里再说一点，如果是单调递增栈的话，那么这两个值就是最小和次小值，不错的性质哦……

代码

#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

const int MAXN = 1e5 + 10;

int n;
int val[MAXN];
stack<int> si;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main(int argc, const char * argv[])
{
    scan_d(n);
    for (int i = 0; i < n; i++)
    {
        scan_d(val[i]);
    }

    int res = 0;

    // 单调递减栈
    for (int i = 0; i < n; i++)
    {
        while (!si.empty() && val[i] > val[si.top()])
        {
            si.pop();
        }
        if (!si.empty())
        {
            res = max(res, val[i] ^ val[si.top()]);
        }
        si.push(i);
    }

    while (!si.empty())
    {
        si.pop();
    }

    // 反向单调递减栈
    for (int i = n - 1; i >= 0; i--)
    {
        while (!si.empty() && val[i] > val[si.top()])
        {
            si.pop();
        }
        if (!si.empty())
        {
            res = max(res, val[i] ^ val[si.top()]);
        }
        si.push(i);
    }

    cout << res << '\n';

    return 0;
}