RMQ问题

RMQ的预处理时间复杂度为nlogn，但是查找的话就是线性的。

https://vjudge.net/contest/228508#problem/B

专题连接

int st[maxm][17];//
int _gcd(int a,int b){return b?_gcd(b,a%b):a;}
void init() {
   for(int j = 1; (1 << j) <= maxm; j++) {//j的范围要根据总的范围为2的几次方来定。
        for(int i = 0; i + (1 << j) - 1 <= maxm; i++) {//这里maxm是总的范围，书上写的n，好恶心，如果是离散好了就是n，没离散就是maxm.
            st[i][j] = _gcd(st[i][j - 1], st[i + (1 << (j - 1)) ][j - 1]);//函数还可以是mix与maxm或者其他很多。
        }　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
   }
}
int query(int l, int r) {
int k = 0;
while((1 << (k + 1)) <= r - l + 1) k++;
return _gcd(st[l][k], st[r - (1 << k) + 1][k]);
}

https://vjudge.net/contest/228508#problem/A

这一题那个while循环注意看一下。注意下二分区间的范围，

右边界== n?????????????????????????????????