[模拟赛] 养花

\(对于 100\% 的数据, n ≤ 10^5，m ≤ 10^5，a_i ≤ 10^5，k_i ≤ 10^5。\)

思路：

考虑2种暴力做法(下文中默认n,m,a,值域同阶)

1. 对于每个k,处理出%k意义下的区间最大值，直接查询即可，时间复杂度为\(O(n^2+n\log_2n)\)
2. 对于每个k,枚举商数i,查询区间内满足值除以k(下取整)等于i的最大值，使用主席树维护。时间复杂度为\(O(n\frac{n}{k}\log_2n)\)

从上面可以看出，暴力2在k很大时效率很高，所以我们考虑2种暴力混合使用。

我们先处理出每个\(k<=W\)的线段树（暴力1），当询问\(k \leq w\)时线段树上查询；否则使用暴力2

时间复杂度为\(O(Wn+\frac{n}{W}n\log_2n)\)

\(O(Wn+\frac{n}{W}n\log_2n)\geq O(n\sqrt{n\log_2n})\),当\(W=\sqrt{n\log_2n}\)时取等

\[\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.} \]

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define Type template<typename T>
# define read read1<ll>()
Type T read1(){
    T t=0;
    char k;
    bool vis=0;
    do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
    while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
    return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout) 
# define SQ 1303
int s,m,a[100005],v[400005],ans[100005];
struct Q{
    int l,r,n;
};
struct node{
    node *l,*r;
    int t;
    node(){l=r=NULL;t=0;}
}*root[100005];
vector<Q>q[100005];
node* L(node *x){return x?x->l:NULL;}
node* R(node *x){return x?x->r:NULL;}
node* ins(node* x,int l,int r,int v){
    node* n=new node();
    if(x)n->l=x->l,n->r=x->r,n->t=x->t;
    ++n->t;
    if(l==r)return n;
    int mid=l+r>>1;
    if(v<=mid)n->l=ins(L(n),l,mid,v);
    else n->r=ins(R(n),mid+1,r,v);
    return n;
}
void build(int l,int r,int d,int& k){
    if(l==r)v[d]=a[l]%k;
    else{//mumumei momom
        int mid=l+r>>1;
        build(l,mid,d<<1,k);
        build(mid+1,r,d<<1|1,k);
        v[d]=max(v[d<<1],v[d<<1|1]);
    }
}
int query(int l,int r,int tl,int tr,int d){
    if(l==tl&&r==tr)return v[d];
    int mid=l+r>>1;
    if(tr<=mid)return query(l,mid,tl,tr,d<<1);
    if(mid<tl)return query(mid+1,r,tl,tr,d<<1|1);
    return max(query(l,mid,tl,mid,d<<1),query(mid+1,r,mid+1,tr,d<<1|1));
}
int SZ(node *x){return x?x->t:0;}
int query(node *x,node *y,int l,int r,int tl,int tr){
    if(SZ(x)==SZ(y))return -1;
    if(tl==tr)return tl;
    int mid=tl+tr>>1;
    if(r<=mid)return query(L(x),L(y),l,r,tl,mid);
    if(mid<l)return query(R(x),R(y),l,r,mid+1,tr);
    int v=query(R(x),R(y),mid+1,r,mid+1,tr);
    if(~v)return v;
    return query(L(x),L(y),l,mid,tl,mid);
}
int main(){
    // fre("flower");
    s=read,m=read;
    for(int i=1;i<=s;++i)
        root[i]=ins(root[i-1],1,100001,a[i]=read);
    for(int i=1;i<=m;++i){
        Q tem;tem.l=read,tem.r=read,tem.n=i;
        q[read].push_back(tem);
    }
    for(int i=1;i<=SQ;++i)
        if(q[i].size()){
            build(1,s,1,i);
            for(int j=0;j<q[i].size();++j){
                ans[q[i][j].n]=query(1,s,q[i][j].l,q[i][j].r,1);
            }
        }
    for(int j=SQ+1;j<=100001;++j){
        for(int i=0;i<=100001/j;++i){
            int l=i*j,r=(i+1)*j-1;if(r>100001)r=100001;
            if(l<1)l=1;
            for(int k=0;k<q[j].size();++k)
                ans[q[j][k].n]=max(ans[q[j][k].n],query(root[q[j][k].l-1],root[q[j][k].r],l,r,1,100001)-i*j);
        }
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}