[Aboi Round 2] 礎の花冠 题解

· · 题解

10pts

直接暴力枚举。

20pts

把询问离线下来，然后做扫描线。

我们发现，对于一个 r 对应的每个分数，最晚的 l 是可以 \mathcal O(V) 的更新的，所以我们直接这么做，可以做到 \mathcal O(nV)。

剩余部分分

这里借用出题人题解的说法：l=1 是给不会算种类数的，n \le 10^5 是给被卡常的。

正解

我们发现 V,n,q 同阶。

我们考虑沿用 20pts 的思路，对询问离线下来然后做扫描线，假设现在扫到了 r 这个位置，对于每一个 x,x < r，我们进行分类讨论。

1. a_x \le a_r

这类我们直接对 a_r 进行整除分块然后统一处理。对于整除分块得到的一个值域区间 [L,R]，我们查询这个值域区间上出现位置的最晚位置，作为答案可以包含这个分数的最晚 l（此处的 l 为询问中的 l），统计完所有分数后把在值域上 a_r 位置的值更新为 r。

假设询问复杂度为 \mathcal O(a)，修改复杂度为 \mathcal O(b)，那么这块的总复杂度就是 \mathcal O(an\sqrt n + bn)，我们根号平衡一下，令 a=1 和 b=\sqrt n，这样子这块的总复杂度就是 \mathcal O(n\sqrt n)，可以接受。

具体写法就是我们对于值域进行分块，每个块内和整块之间都建立 ST 表，这样子更新一个位置就是要重建单块内的 ST 表和整块之间的 ST 表，我们只对涉及到修改位置的部分进行重建，总复杂度为 \sum\limits_{i=0}^{\lfloor\log_2\sqrt n\rfloor}2^i=\mathcal O(\sqrt n)。

2. a_x > a_r

我们也分两种情况讨论。

一、a_r>\sqrt n

我们枚举 a_r 的所有倍数，值域 [ka_r,(k+1)a_r) 内出现最晚的数可以拿来统计 k，这部分复杂度同整除分块复杂度，为 \mathcal O(n\sqrt n)。

二、a_r\le\sqrt n

令 pos_v 表示值为 v 的位置中至今最靠后的一个，那么我们直接从 pos_{a_r}+1 扫到 r，然后暴力统计，因为这样的数最多 \sqrt n 个，所以这部分的复杂度为 \mathcal O(n\sqrt n)，还有别忘了更新 pos_{a_r} 为 r。

所以对于 a_x>a_r，我们也以 \mathcal O(n\sqrt n) 做完了。

答案统计

上文我们只说统计进答案，但是我们没有说怎么统计。其实非常简单，我们维护一个值域分块，同时我们需要记录每个分数的最晚 l，我们每次修改就是在分块上的旧的最晚 l 位置上 -1，然后在新的最晚 l 位置上 +1，而对于某个 i，若 r_i=r，那么 ans_i=sum(l_i,r_i)，其中 sum(l,r) 表示在值域分块上对 [l,r] 求和，其含义为对所有 l 符合条件的分数进行计数，这部分用分块而不是别的数据结构还是为了保证修改的复杂度，这部分的最后复杂度为 \mathcal O(1) 修改 \mathcal O(\sqrt n) 查询，总共查 \mathcal O(n) 次。

综上，每部分的复杂度均为 \mathcal O(n\sqrt n)，故总复杂度为 \mathcal O(n\sqrt n)。

整除分块需要卡常，记得做一下，其思路就是如果说整除分块得到的那个 [L,R] 所代表的值大于 \sqrt a_r，那么显然这段的值只能为 1，这样可以避免除法，卡常这一块。

实现代码

#include <bits/stdc++.h>
using namespace std;
namespace MySpace{
    #define lowbit(x) (x&(-x))
    #define sqrt sqrtl
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    #define whileu(p) while (p--)
    #define forl(a,b,c) for (auto a=b;a<=c;a=a+1)
    #define chk(x,y) x=x<y?y:x
    #define max(x,y) (x<y?y:x)
    inline void read() {}
    template <typename T, typename... R>
    inline void read(T &x,R &... oth){
        x=0;T f=1;
        char c=getchar();
        while(c<'0' || c>'9') {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
        x*=f;
        read(oth...);
        return;
    }
    template<typename T>
    T qpow(T a,T n,T p){
        T res=1;
        while (n){
            if (n&1) res=1ll*res*a%p;
            a=1ll*a*a%p;
            n>>=1;
        }
        return res;
    }
    template<typename T>
    T gcd(T a,T b){return (b>0?gcd(b,a%b):a);}
    template<typename T>
    T exgcd(T a,T b,T& x,T& y){
    if (b<=0ll){
            x=1ll,y=0ll;
            return a;
        }
        T t=x;
        T d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;
    }
    template<typename T>
    T inv(T a,T p){
        if (a==1) return 1ll;
        T x,y;
        if (exgcd(a,p,x,y)!=1ll) return -1ll;
        else return (x+p)%p;
    }
}
using namespace MySpace;

const int N=400005,V=400000,B=600,blk=800,G=N/blk+5;
int n,m,tot,L[G],R[G];
int a[N],bl[N],ans[N],lt[N],pr[N];
vector<pair<int,int> > q[N];

struct blk1{
    int S[G],c[N];
    inline void add(int x,int v){
        if(x) S[bl[x]]+=v,c[x]+=v;
    }
    inline int ask(int x){
        int res=0;
        for(int i=x;i<=R[bl[x]];++i) res+=c[i];
        for(int i=bl[x]+1;i<=tot;++i) res+=S[i];
        return res;
    }
}T;

struct blk2{
    int M[G],P[N],S[N],g[N];
    inline int ask(int l,int r){
        r=min(r,V);
        if(r-l+1<=blk){
            int res=0;
            for(int i=l;i<=r;++i) chk(res,g[i]);
            return res;
        }
        int res=max(S[l],P[r]);
        for(int i=bl[l]+1;i<bl[r];++i) chk(res,M[i]);
        return res;
    }
    inline void mod(int x,int v){
        g[x]=v,M[bl[x]]=v;
        for(int i=x;i<=R[bl[x]];++i) P[i]=v;
        for(int i=L[bl[x]];i<=x;++i) S[i]=v;
    }
}F;

inline void C(int x,int y){
    if(lt[x]<y) T.add(lt[x],-1),T.add(lt[x]=y,1);
}

signed main(){
    read(n,m);
    tot=(V-1)/blk+1;
    bl[0]=1;
    for(int i=1;i<=V;++i) bl[i]=(i-1)/blk+1;
    for(int i=1;i<=tot;++i){
        L[i]=R[i-1]+1;
        R[i]=i*blk;
    }
    L[1]=0;
    R[tot]=V;

    for(int i=1;i<=n;++i) read(a[i]);
    for(int i=1;i<=m;++i){
        int l,r;
        read(l);
        read(r);
        q[r].push_back({l,i});
    }

    for(int i=1;i<=n;++i){
        const int v=a[i],sq=sqrt(v);
        F.mod(v,i);
        C(0,F.ask(v+1,V));

        if(a[i]>1000){
            for(int l=1,r,P=0;l<=v;C(P,F.ask(l,r)),l=r+1){
                if(l>sq) --P,r=v/P;
                else P=v/l,r=l;
            }
        }else{
            for(int l=1,r,P=0;l<=v;C(P,F.ask(l,r)),l=r+1){
                P=v/l,r=v/P;
            }
        }

        if(v>=B){
            for(int j=0,P=0,pos;j<=V;++P,j+=v){
                pos=F.ask(j,j+v-1);
                C(P,pos);
            }
        }else{
            for(int j=pr[v]+1;j<=i;++j){
                C(a[j]/v,j);
            }
        }

        pr[a[i]]=i;

        for(unsigned int j=0;j<q[i].size();++j){
            ans[q[i][j].second]=T.ask(q[i][j].first);
        }
    }

    for(int i=1;i<=m;++i){
        printf("%d\n",ans[i]);
    }
    return 0;
}