hdu 5875 Function ST+二分

Function

引理：
我们称 $X\ge M$ 时 $X\ mod\ M$ 为一次有效的取模，则 $X$ 在 $\lceil log_{2}X\rceil$ 次有效的取模后一定变为 0 。
简要说明：
考虑最坏情况，取 $M=\lfloor\frac{X}{2}\rfloor+1$ ，$X->\lfloor\frac{X-1}{2}\rfloor$
（当 $M’>M$ 或 $M’<M$ 时，$X$ 都会变得更小）

题解：
考虑到 $a[l]$ 有效取模次数是 $log$ 级别的，所以只需要快速找出下一次有效的取模
即，每次寻找不大于当前数的最靠左的数
可以二分右端点，并询问区间内最小的数
使用ST维护，预处理 $O(NlogN)$ ，询问 $O(1)$
取模 $O(logX)$ 次，二分 $O(logN)$ 次，rmq $O(1)$ ，每个case复杂度为 $O(M*logX*logN)$
ST好久没写。。。可能失败的二分也好久没写。。。T了好多好多次。。。代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100010;
int st[N][25];

void st_init(int n)
{
    for (int i=1;(1<<i)<=n;i++)
        for (int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}

int st_query(int l,int r)
{
    int k=0;
    while ((1<<(k+1))<=r-l+1) k++;
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

int bsearch(int l,int r,int lim)
{
    int res=r+1;
    while (l<=r) {
        int m=(l+r)>>1;
        if (st_query(l,m)>lim) l=m+1;
        //区间最小值大于当前值，即区间所有数大于当前值
        else r=m-1,res=m;
    }
    return res;
}

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&st[i][0]);
        st_init(n);
        scanf("%d",&m);
        while (m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            int res=st[l++][0];
            while (l<=r&&res) {
                l=bsearch(l,r,res);
                if (l<=r) {
                    res%=st[l++][0];
                }
            }
            printf("%d\n",res);
        }
    }
    return 0;
}