浅谈st表

void init()
{
    for(int i=1;i<=lg[n];i++)
    {
        for(int j=1;j+(1< 
st表查询： 
int l,r;
scanf("%d %d",&l,&r);
int len=lg[r-l+1];
int x=max(h[l][len],h[r-(1< 
例题：codeforces 359D - Pair of Numbers 
题意： 

 找到最长的区间【L，R】，并且满足区间中存在一个能将所有数整除的数，输出所有满足的答案的起始点。
 
题解： 
我们发现区间长度存在单调性，故对区间长度进行二分。
 在check函数中对该长度的每一个起点进行枚举。发现区间的最大公约数等于区间的最小值时，该区间成立。我们就只需要对该区间的最小值和最大公约数用st表维护。O(1)查询即可。
 
代码： 
#include
using namespace std;
typedef long long LL;
const LL N =3e5+5;
int a[N],g[N][20],st[N][20],lg[N]={-1},n,ans;
vectorres;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
void init()
{
    for(int i=1;i<=lg[n];i++)
    {
        for(int j=1;j+(1<vec;
    int len=lg[x+1];
    for(int i=1;i+x<=n;i++)
    {
        int minn=min(st[i][len],st[i+x-(1<=ans) res=vec;
        return 1;
    }
    return 0;
}
void solve()
{

    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        lg[i]=lg[i/2]+1;
        g[i][0]=st[i][0]=a[i];
        res.push_back(i);
    }
    init();
    int l=0,r=n-1;
    while(l>1;
        if(check(mid))
        {
            ans=max(ans,mid);
            l=mid;
        }
        else r=mid-1;
    }
    printf("%d %dn",res.size(),ans);
    for(auto i:res) printf("%d ",i);
}
int main()
{
    int t=1;
    //scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}