倍增求区间最大值

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=1e4+5;
 9 
10 int fa[N][16],maxval[N][16];
11 int a[N];
12 int n;
13 
14 int getmax(int x,int y) {
15     if(x==y) return a[x];
16     int t=y-x,ans=0;
17     for(int i=15;i>=0;i--) {
18         if(t&(1<<i)) {
19             ans=max(ans,maxval[x][i]);
20             x=fa[x][i];
21         }
22     }
23     return ans;
24 }
25 
26 int main() {
27     scanf("%d",&n);
28     for(int i=1;i<=n;i++) {
29         scanf("%d",&a[i]);
30     }
31     for(int i=1;i<n;i++) fa[i][0]=i+1;
32     for(int i=n;i>=1;i--) {
33         for(int j=1;j<=15;j++) {
34             fa[i][j]=fa[fa[i][j-1]][j-1];
35         }
36     }
37     for(int i=1;i<=n;i++) maxval[i][0]=max(a[i],a[i+1]);
38     for(int i=n;i>=1;i--) {
39         for(int j=1;j<=15;j++) {
40             maxval[i][j]=max(maxval[i][j-1],maxval[fa[i][j-1]][j-1]);
41         }
42     }
43     int q;
44     scanf("%d",&q);
45     while(q--) {
46         int x,y;
47         scanf("%d%d",&x,&y);
48         printf("%d\n",getmax(x,y));
49     }
50     return 0;
51 }