维护区间最小值位置ST表
<pre><code class="language-cpp">const int maxn = 3e5+5;
int st[maxn][25];
int n
ll a[maxn];
int lg[300005] = {-1};
void getlog(){
for(int i = 1; i <= 300005; i++) lg[i] = lg[i/2] + 1;
return;
}
void init(){
for(int i = 1; i <= n; i++){
st[i][0] = i; //st表存数组下标
}
for(int j = 1; (1 << j) <= n; j++){
for(int i = 1; i + (1 << (j-1)) <= n; i++){
st[i][j] = (a[st[i][j-1]] < a[st[i+(1<<(j-1))][j-1]])? st[i][j-1]: st[i+(1<<(j-1))][j-1]; //此条语句
}
}
}
int query(int l, int r){
int k = lg[r-l+1];
return (a[st[l][k]] < a[st[r-(1<<k)+1][k]])? st[l][k]: st[r-(1<<k)+1][k]; //此条语句
}</code></pre>