ConanKIDの小窝

ConanKIDの小窝

题解 CF280B 【Maximum Xor Secondary】

posted on 2021-01-22 14:57:28 | under 题解 |

其他题解貌似不是很清楚,蒟蒻来写一篇吧

这题要求的东西似乎很诡异

我们不妨换个思路,对于每个数,固定其为选出的序列中的次大值,在它左边去找最大值,也就是它左边离它最近的比它大的数

这样的话,我们就要对于每个$a_i$,找到一个最大的$j$,使得$j<i$且$a_j>a_i$

看到这个式子就想到单调栈了

不懂单调栈的话,左转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;
}