st表模板

点击查看代码

#include <bits/stdc++.h>using namespace std;const int N = 2000001;
const int logN = 21;int f[N][logN + 1], lg[N + 1];
//vector<int>可能会爆内存void pre(){lg[1] = 0;lg[2] = 1;for(int i = 3; i < N; i ++){lg[i] = lg[i >> 1] + 1;}
}void solve(){int n,m;cin >> n >> m;for(int i = 1; i <= n; i ++){cin >> f[i][0];}pre();for(int j = 1; j <= logN; j ++){for(int i = 1; i + (1 << j) - 1 <= n; i ++){f[i][j] = max(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]);}}while(m --){int x,y;cin >> x >> y;int s = lg[y - x + 1];cout << max(f[x][s],f[y - (1 << s) + 1][s]) << '\n';}
}int main(){ios::sync_with_stdio(0);cin.tie(0);int t = 1;//cin >> t;while(t --){solve();}return 0;
}