ST表

当数学看吧

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=5e5+5;
 5 const int K=log(N)/log(2)+1;
 6 int a[N],lg[N],mi[N][K],mx[N][K],n; 
 7 ll ans;
 8 int main()
 9 {
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)
12     {
13         scanf("%d",&a[i]);
14         mi[i][0]=mx[i][0]=a[i];
15     }
16     lg[0]=-1;
17     for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
18      
19     for(int j=1;j<=lg[n];j++)
20     for(int i=1;i+(1<1<=n;i++)
21     {
22         mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
23         mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
24     }
25     int len=lg[r-l+1];
26     ans=max(mx[l][len],mx[r-(1<1][len]);
27     return 0;
28 }