用的是分块 RMQ 的写法

最后一个 $substack$ MLE 了一半，怀疑是对 $\gt \sqrt k$ 的写挂了

#include<bits/stdc++.h>
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb emplace_back
#define go(it) for(auto &it:as[x])
#define il inline
using namespace std;

const int N=3e5+10,M=1e3,B=550,V=1e5+10;
int n,m;
int a[N],ans[N],st[M],ed[M],c[N];
struct node{int l,r,id;};
vector<node> q[V],qs[V];
bitset<N> bs;

il int fr(){
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
il void fw(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
il int max(int a,int b){return a>b?a:b;}
il int min(int a,int b){return a<b?a:b;}

struct Block_Min
{
    int Min[M],b[N];
    int query(int l,int r,int k)
    {
        int L=c[l]+1,R=c[r]-1,ans=2e9;
        if(c[l]==c[r])
        {
            for(int i=l;i<=r;i++) ans=min(ans,b[i]);
            return ans;
        }
        for(int i=L;i<=R;i++) ans=min(ans,Min[i]);
        for(int i=l;i<=ed[c[l]];i++) ans=min(ans,b[i]);
        for(int i=st[c[r]];i<=r;i++) ans=min(ans,b[i]);
        return ans;
    }
    void build(int k)
    {
        memset(Min,0x3f,sizeof Min);
        for(int i=1;i<=n;i++)
            Min[c[i]]=min(Min[c[i]],b[i]=a[i]%k);
    }
    void solve()
    {
        for(int i=1;i<=n;i++) c[i]=(i-1)/B+1;
        for(int k=1;k<=c[n];k++)
            st[k]=(k-1)*B+1,ed[k]=k*B;
        ed[c[n]]=n;

        for(int k=1;k<=B;k++)
        {
            if(!qs[k].size()) continue;
            build(k);
            for(node &v:qs[k])
                ans[v.id]=query(v.l,v.r,k);
        }
    }
}B1;

struct Block_Max
{
    int Min[10][M],lg[N],pre[N],suf[N];
    vector<int> add[N];

    void mdf(int p)
    {
        int b=c[p];
        for(int k=0;k<=lg[c[n]];k++)
            for(int i=max(b-(1<<k)+1,1);i<=b && i+(1<<k)-1<=c[n];i++)
                Min[k][i]=a[p];
        for(int i=st[b];i<=p;i++) suf[i]=a[p];
        for(int i=p;i<=ed[b];i++) pre[i]=a[p];
    }
    int ST(int l,int r)
    {
        if(l>r) return 2e9;
        int d=lg[r-l+1];
        return min(Min[d][l],Min[d][r-(1<<d)+1]);
    }
    int query(int l,int r)
    {
        if(c[l]==c[r])
        {
            int res=2e9;
            for(int i=l;i<=r;i++)
                if(bs.test(i)) res=min(res,a[i]);
            return res;
        }
        return min({suf[l],pre[r],ST(c[l]+1,c[r]-1)});
    }

    void solve()
    {
        lg[0]=-1;
        memset(Min,0x3f,sizeof Min);
        memset(pre,0x3f,sizeof pre);
        memset(suf,0x3f,sizeof suf);
        for(int i=1;i<=n;i++)
            add[a[i]].pb(i),lg[i]=lg[i>>1]+1;

        for(int v=1e5;~v;v--)
        {
            for(int &p:add[v]) mdf(p),bs.set(p,1);
            for(node &k:q[v])
                ans[k.id]=min(ans[k.id],query(k.l,k.r)-v);
        }
    }
}B2;

int main()
{
    n=fr(),m=fr();
    for(int i=1;i<=n;i++) a[i]=fr();

    memset(ans,0x3f,sizeof ans);
    for(int i=1;i<=m;i++)
    {
        int l=fr(),r=fr(),k=fr();
        if(k<=B) qs[k].pb(node({l,r,i}));
        else
            for(int v=0;v<=1e5;v+=k)
                q[v].pb(node({l,r,i}));
    }

    B1.solve();
    B2.solve();
    for(int i=1;i<=m;i++) fw(ans[i]),nl;
    return 0;
}