牛牛的魔法值 题解

题目大意：

给你一个长度为n的序列，问你，这个序列的所有连续子序列中，子序列的最大值和次大值的异或和最大是多少？

分析：

我们直接枚举所有连续子序列肯定布星，我们换一个枚举方向。

我们考虑枚举子序列的次大值，那么，我们只需要找到一个当前枚举的点的值大的那个点作为最大值即可。

我们注意到，因为我们枚举的是次大值，所以它所处在的子序列中，比它大的点有且只有一个。所以，我们找到这个点左边，离它最近的比它大的点的值和这个点右边，离它最近的比它大的点的值，那么连续子序列的最大值必然是这两个值中的一个。我们每个都算下取最大即可。

至于如果求这两个值，随便搞搞就行，基本就不需要动脑了/x

我是用的st表+二分搞的。

代码:

class Solution {
public:
    int s[100001][20];
    inline int calc(int l,int r){
        int len=(r-l+1),now=0;
        while(len>=(1<<(now+1))){
            ++now;
        }
        return max(s[l][now],s[r-(1<<now)+1][now]);
    }
    int solve(int n, vector<int>& a) {
        for(int i=0;i<n;++i){
            s[i][0]=a[i];
        }
        int lon=1;
        for(int i=1;i<20;++i){
            lon<<=1;
            for(int j=0;j<n;++j){
                int r=j+lon-1;
                if(r>n){
                    break;
                }
                s[j][i]=max(s[j][i-1],s[r-(lon/2)+1][i-1]);
            }
        }
        int ans=0;
        for(int i=0;i<n;++i){
            int l=0,r=i-1,res=-1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(calc(mid,i-1)>a[i]){
                    res=mid;l=mid+1;
                }else{
                    r=mid-1;
                }
            }
            if(res!=-1){
                ans=max(ans,(a[i]^a[res]));
            }
            l=i+1,r=n-1,res=-1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(calc(i+1,mid)>a[i]){
                    res=mid,r=mid-1;
                }else{
                    l=mid+1;
                }
            }
            if(res!=-1){
                ans=max(ans,(a[i]^a[res]));
            }
        }
        return ans;
    }
};

我们还可以使用单调队列，这样，复杂度就只有了！

代码:

class Solution {
public:
    int que[100001],l=1,r=0;
    int solve(int n, vector<int>& a) {
        que[++r]=a[1];int ans=0;
        for(int i=2;i<=n;++i){
            while(l<=r&&que[r]<=a[i]){
                --r;
            }
            if(l<=r){
                ans=max(ans,(a[i]^que[r]));
            }
            que[++r]=a[i];
        }
        l=1,r=0;
        que[++r]=a[n];
        for(int i=n-1;i;--i){
            while(l<=r&&que[r]<=a[i]){
                --r;
            }
            if(l<=r){
                ans=max(ans,(a[i]^que[r]));
            }
            que[++r]=a[i];
        }
        return ans;
    }
};

事实上，只需要使用单调栈就行了qwq

代码:

class Solution {
public:
    int sta[100001],top=0;
    int solve(int n, vector<int>& a) {
        sta[++top]=a[1];int ans=0;
        for(int i=2;i<=n;++i){
            while(top&&sta[top]<=a[i]){
                --top;
            }
            if(top){
                ans=max(ans,(a[i]^sta[top]));
            }
            sta[++top]=a[i];
        }
        top=0;
        sta[++top]=a[n];
        for(int i=n-1;i;--i){
            while(top&&sta[top]<=a[i]){
                --top;
            }
            if(top){
                ans=max(ans,(a[i]^sta[top]));
            }
            sta[++top]=a[i];
        }
        return ans;
    }
};