RMQ

范围最小值问题(Range Minimum Query)
常用Tarjan的Sparse-Table算法，预处理时间为(O(nlogn))，查询为(O(1))

int rmq[maxn][maxn];
void rmq_init(int a[],int l,int r)
{
  for(int i=0;(1<<i)<=r-l+1;++i)
    for(int j=l;j+(1<<i)-1<=r;++j)
      rmq[j][i]=(i==0)?a[j]:min(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
}
int rmq_query(int l,int r)
{
  int tmp=0;
  while((1<<(tmp+1))<=r-l+1)tmp++;
  return min(rmq[l][tmp],rmq[r-(1<<tmp)+1][tmp]);
}