题解 CF280B 【Maximum Xor Secondary】

其他题解貌似不是很清楚，蒟蒻来写一篇吧 这题要求的东西似乎很诡异 我们不妨换个思路，对于每个数，固定其为选出的序列中的次大值，在它左边去找最大值，也就是它左边离它最近的比它大的数 这样的话，我们就要对于每个$a_i$，找到一个最大的$j$，使得$j<i$且$a_j>a_i$ 看到这个式子就想到单调栈了 不懂单调栈的话，左转[P5788](https://www.luogu.com.cn/problem/P5788) 当然我们的最大值也可以在次大值的右边，于是正着跑一遍单调栈，再反着跑一遍，在所有的答案中取一个$\max$，就是最终结果 时间复杂度为$O(n)$ ``` #include<bits/stdc++.h> using namespace std; int n; int a[100005]; stack<int>s; int ans=-1e9; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ while(!s.empty()&&s.top()<a[i])s.pop();//维护单调栈，找到距离a[i]最近的大于a[i]的数 if(!s.empty())ans=max(ans,s.top()^a[i]);//答案打擂台取最大值 s.push(a[i]); } while(!s.empty())s.pop(); for(int i=n;i>=1;i--){//同上 while(!s.empty()&&s.top()<a[i])s.pop(); if(!s.empty())ans=max(ans,s.top()^a[i]); s.push(a[i]); } cout<<ans<<endl; return 0; } ```