题解：P13984 数列分块入门 9

· · 题解

#6285. 数列分块入门 9 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及询问区间的最小众数。

技巧

方法 1

分块，块长为 T。预处理 f_{i,j,k} 表示块 i 到块 j 内数字 k 出现的次数，g_{i,j} 表示块 i 到块 j 的众数。

对于 f_{i,j,k} 可以继承 f_{i,j-1,k} 的结果，时间复杂度 \mathcal{O}((\frac{n}{T})^2(n+T))=\mathcal{O}(\frac{n^3}{T^2})。对于 g_{i,j} 直接对于每对 (i,j) 利用 f 求出众数即可，时间复杂度 \mathcal{O}((\frac{n}{T})^2n)=\mathcal{O}(\frac{n^3}{T^2})

查询时，先用 f,g 求出整块的众数与其数量，然后暴力枚举散块的每个数，修改整块的 f 来计算众数，最后别忘了把 f 改回来。时间复杂度 \mathcal{O}(T)。

时间复杂度。预处理 \mathcal{O}(\frac{n^3}{T^2})，询问 \mathcal{O}(T)。若 m 与 n 同阶，最优块长 T 应使 \frac{n^3}{T^2}=nT，则 T=\sqrt[3]{n^2}=n^{\frac{2}{3}}。总体复杂度 \mathcal{O}(n^{\frac{5}{3}})。

方法 2

分块，块长为 T。预处理 f_{i,j} 表示块 i 到块 j 的众数，id_a 表示 a 出现的下标。

对于 f_{i,j} 枚举 i，枚举 [be_i,n] 的所有数，利用 c_{i,j} 表示以块 i 为左端点，此时 j 出现了几次，求出每对 (i,j) 的众数，时间复杂度 \mathcal{O}(\frac{n}{T}n)=\mathcal{O}(\frac{n^2}{T})。对于 id_a 用 vector 即可，时间复杂度 \mathcal{O}(n)，查询一个数在一段区间内的个数时间复杂度 \mathcal{O}(\log n)。

查询时，由于众数一定是整块的众数、散块的所有数中的一个，所以先用 f,id 在 \mathcal{O}(\log n) 的时间复杂度下求出整块的众数及其数量，然后暴力枚举散块的每个数，用 id 求出这个数的数量，更新众数。时间复杂度 \mathcal{O}(\log n+T\log n)=\mathcal{O}(T\log n)。

时间复杂度。预处理 \mathcal{O}(\frac{n^2}{T}+n)=\mathcal{O}(\frac{n^2}{T})，询问 \mathcal{O}(T\log n)。若 m 与 n 同阶，最优块长 T 应使 \frac{n^2}{T}=nT\log n，则 T=\sqrt{\frac{n}{\log n}}。总体复杂度 \mathcal{O}(n\sqrt{\frac{n}{\log n}}\log n)=\mathcal{O}(n\sqrt{n\log n})=\mathcal{O}(n^{\frac{3}{2}}\sqrt{\log n})。

关于两者时间复杂度对比

对比 \mathcal{O}(n^{\frac{3}{2}}\sqrt{\log n}) 和 \mathcal{O}(n^{\frac{5}{3}})，约分一下就是 \sqrt{\log n} 和 n^{\frac{1}{6}}。

结论：小数据后者优，大数据前者优。本题前者过不了，后者需要卡一点常。

使 T=\frac{\sqrt{\frac{n}{\log n}}}{1.2} 可以卡过本题。

代码

const int N=3e5+3,T=2666+3;
int n,m,a[N],L,len,tot,bel[N],be[T],en[T],f[T][T];
vector<int>has,id[N];

void work(int &ans,int &cnt,int Ans,int Cnt){
    if(Cnt>cnt||Cnt==cnt&&Ans<ans){
        cnt=Cnt,ans=Ans;
    }
}
int get(int l,int r,int val){
    return upper_bound(id[val].begin(),id[val].end(),r)-lower_bound(id[val].begin(),id[val].end(),l);
}
void init(){
    L=sqrt(n*log(n)/log(2))/1.2,len=n/max(1,L),tot=L;
    for(int i=1;i<=L;i++){
        be[i]=en[i-1]+1,en[i]=i*len;
    }
    if(en[L]<n){
        tot++;
        be[tot]=en[tot-1]+1;
        en[tot]=n;
    }
    for(int i=1;i<=tot;i++){
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
    for(int i=1;i<=tot;i++){
        int ans=0,cnt=0;
        vector<int> c(n+5);
        for(int j=be[i];j<=n;j++){
            work(ans,cnt,a[j],++c[a[j]]);
            f[i][bel[j]]=ans;
        }
    }
}
int query(int l,int r){
    int ans=0,cnt=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            work(ans,cnt,a[i],get(l,r,a[i]));
        }
        return ans;
    }
    if(bel[l]+1<=bel[r]-1){
        work(ans,cnt,f[bel[l]+1][bel[r]-1],get(l,r,f[bel[l]+1][bel[r]-1]));
    }
    for(int i=l;i<=en[bel[l]];i++){
        work(ans,cnt,a[i],get(l,r,a[i]));
    }
    for(int i=be[bel[r]];i<=r;i++){
        work(ans,cnt,a[i],get(l,r,a[i]));
    }
    return ans;
}

signed main(){
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        has.pb(a[i]);
    }
    sort(all(has)),has.erase(unique(all(has)),has.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(all(has),a[i])-has.begin()+1;
        id[a[i]].pb(i);
    }
    init();
    for(int l,r;m--;){
        cin>>l>>r;
        cout<<has[query(l,r)-1]<<"\n";
    }
    return 0;
}