51nod1423 最大二“货” 单调队列

51nod1423 最大二“货”
单调队列

考虑次大值在最大值前面的情况这样出栈时就可以两个数异或一下维护一个单调递减的单调队列
出栈的数当做次大值进栈的数当做最大值
但是这样只考虑了一种情况还要考虑最大值在次大值前面的情况，这样只要反向在做一遍就行了，然后取最大值

这题还有个重要的条件就是没有两个数相等的情况如果有的话次大值和较大值就麻烦了

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip> 
 8 #include <iostream> 
 9 using namespace std ; 
10 
11 const int maxn = 1e5 + 11 ; 
12 int n,top,ans,t ;
13 int a[maxn],st[maxn] ;  
14 
15 inline int read() 
16 {
17     int x = 0 , f = 1 ; 
18     char ch = getchar() ; 
19     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
20     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; }
21     return x * f ; 
22 }
23 
24 inline void solve() 
25 { 
26     for(int i=1;i<=n;i++) 
27     {
28         while(top&&st[ top ] <= a[ i ] )   //其实每一个数都是不同的  ,所以等号是不必要的  
29         {
30             ans = max( ans,a[ i ] ^ st[ top ] ) ; 
31             top-- ; 
32         }
33         st[++top] = a[ i ] ; 
34     }
35 }
36 
37 int main() 
38 {
39     while(~scanf("%d",&n)) 
40     {
41         ans = -1 ; 
42         for(int i=1;i<=n;i++) a[ i ] =read() ; 
43         solve() ; 
44         for(int i=1,zz = n/2;i<=zz;i++) { t = a[ i ]; a[ i ] = a[ n-i+1 ] ; a[ n-i+1 ] = t ; } 
45         solve() ; 
46         printf("%d
",ans) ; 
47     } 
48     
49     return 0 ; 
50 }