HDU 5875 二分+st表

http://acm.hdu.edu.cn/showproblem.php?pid=5875

题意 ：数组一个，Q组询问，给你l和r，问A[ l ]%A[ l+1 ]......%A[ r ]   

思路：下降幅度至少模一个有用的数（比当前数小的数）下降1/2。。。所以就是找一个区间里比一个数小的最左的数字是什么。。这个问题就可以用st表+二分解决

    通过ST表o1得到一个区间最小的数，这样来作为二分的判断条件。这里稍微注意一下二分可能是没有答案的就可以了。

    （懒到现在才写blog、、、存一下代码、、）

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
#define MAX 100005
const int INF=1e9+7;
int n,m;
int a[MAX];

const int MAXN = 100010;
int dp[MAXN][20];
int mm[MAXN]; //初始化RMQ,  b数组下标从1开始，从0开始简单修改

void initRMQ(int n,int b[]){
    mm[0] = -1;        //查询最大值
    for(int i = 1; i <= n; i++){
        mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
        dp[i][0] = b[i];
    }
    for(int j = 1; j <= mm[n]; j++)
        for(int i = 1; i + (1<<j) -1 <= n; i++)
            dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int x,int y){
    int k = mm[y-x+1];
    return min(dp[x][k],dp[y-(1<<k)+1][k]);
}

int query(int s,int t,int x) {
    int res=0;
    int l=s,r=t;
    while(l<=r){
        int mid=(l+r)/2;
        if(rmq(l,mid)<=x)
            r=mid-1;
        else
            l=mid+1;
    }
    if(l<=t&&a[l]<=x)
        return l;
    else
        return INF;
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        initRMQ(n,a);
        scanf("%d",&m);
        int l,r;
        for(int i=0;i<m;i++){
            scanf("%d%d",&l,&r);
            if(l==r){
                printf("%d
",a[l]);
            }
            else{
                int x=a[l];
                while(l<r){
                    l=query(l+1,r,x);
                    if(l!=INF) x%=a[l];
                }
                printf("%d
",x);
            }
        }
    }
    return 0;
}