题解：P13984 数列分块入门 9

· · 题解

upd on 11/07：修改了代码里的小错误。感谢 @kohahahara。

大部分离线区间问题都可以使用莫队解决，这里说一个不用莫队且支持在线的做法。

做法

首先注意到一个性质：答案如果不是中间整块的众数，那答案一定在两边的散块中出现过。这个我认为比较显然。

首先离散化，这样值域就变成了 [1,N]。

预处理 cnt[i][j] 表示前 i 个块中 j 出现过的次数。res[i][j] 表示第 [i,j] 块的最小众数。假设块长为 B，这些都可以以 \Theta(\dfrac{N^2}{B}) 的复杂度处理。

每次询问时，维护一个桶，把散块中的数依次添加，更新答案。但是这个桶我们显然不能每一次询问都全清一遍，这样复杂度就炸了。考虑到候选的答案只有 B 个，所以我们只需要把这 B 个数的次数记录到桶里。复杂度为 \Theta(nB)

我们来求块长，预处理部分是 \Theta(\dfrac{N^2}{B})，询问一共是 \Theta(nB) 的。使用均值不等式，取等条件为 B=\sqrt n，所以复杂度为 \Theta(n\sqrt n)。

代码

注意要输出离散化前的原始值。

#include<bits/stdc++.h>
//#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
    int x=0,y=1;
    char e=getchar();
    while(e<'0'||e>'9') {
        if(e=='-')y=-1;
        e=getchar();
    }
    while(e>='0'&&e<='9') {
        x=(x<<1)+(x<<3)+(e^'0');
        e=getchar();
    }
    return x*y;
}
const int N=300005,B=550;
int n,m,A[N],a[N],b[N];
int L[B],R[B],bel[N],cnt[B][N],res[B][B];
int t[N];
void build() {
    int len=sqrt(n);
    for(int i=1; i<=n; ++i) {
        bel[i]=(i-1)/len+1;
        if(bel[i]!=bel[i-1]) {
            L[bel[i]]=i;
            R[bel[i-1]]=i-1;
        }
    }
    R[bel[n]]=n;
    int tot=bel[n];
    for(int i=1; i<=tot; ++i) {
        for(int j=1; j<=n; ++j) {
            cnt[i][j]=cnt[i-1][j];
        }
        for(int j=L[i]; j<=R[i]; ++j) {
            ++cnt[i][a[j]];
        }
    }
    for(int i=1; i<=tot; ++i) {
        memset(t,0,sizeof t);
        int mx=0,who=1e9;
        for(int j=i; j<=tot; ++j) {
            for(int k=L[j]; k<=R[j]; ++k) {
                ++t[a[k]];
                if(t[a[k]]>mx||(t[a[k]]==mx&&a[k]<who)) {
                    mx=t[a[k]];
                    who=a[k];
                }
            }
            res[i][j]=who;
        }
    }
}
int ask(int l,int r) {
    int p=bel[l],q=bel[r];
    int mx,who;
    if(p==q) {
        mx=0,who=1e9;
        for(int i=l; i<=r; ++i)t[a[i]]=0;
        for(int i=l; i<=r; ++i) {
            ++t[a[i]];
            if(t[a[i]]>mx||(t[a[i]]==mx&&a[i]<who)) {
                mx=t[a[i]];
                who=a[i];
            }
        }
    } else {
        //cnt[q-1]-cnt[p]
        who=res[p+1][q-1];
        mx=cnt[q-1][who]-cnt[p][who];
        if(p+1>q-1)who=1e9;
        for(int i=l; i<=R[p]; ++i) {
            t[a[i]]=cnt[q-1][a[i]]-cnt[p][a[i]];
            if(a[i]==who)++mx;
        }
        for(int i=L[q]; i<=r; ++i) {
            t[a[i]]=cnt[q-1][a[i]]-cnt[p][a[i]];
            if(a[i]==who)++mx;
        }
        for(int i=l; i<=R[p]; ++i) {
            ++t[a[i]];
            if(t[a[i]]>mx||(t[a[i]]==mx&&a[i]<who)) {
                mx=t[a[i]];
                who=a[i];
            }
        }
        for(int i=L[q]; i<=r; ++i) {
            ++t[a[i]];
            if(t[a[i]]>mx||(t[a[i]]==mx&&a[i]<who)) {
                mx=t[a[i]];
                who=a[i];
            }
        }
    }
    return who;
}
signed main() {
    R(n);
    for(int i=1; i<=n; ++i) {
        R(a[i]);
        b[i]=a[i];
    }
    //a是离散化后的值
    sort(b+1,b+1+n);
    int tt=unique(b+1,b+1+n)-b-1;
    for(int i=1; i<=n; ++i) {
        int u=lower_bound(b+1,b+1+tt,a[i])-b;
        A[u]=a[i];
        a[i]=u;
    }
    //A是原始值
    build();
    int ans=0;
    for(int i=1; i<=n; ++i) {
        int R(l),R(r);
        int u=ask(l,r);//rank
        ans=A[u];
        cout<<ans<<"\n";
    }
    return 0;
}