题解：P13984 数列分块入门 9

· · 题解

upd on 9/20：修正了拼写错误，增加了时间复杂度证明。

解析

这道题一看求众数，就知道可以回滚莫队做。

由于是众数问题，便使用只增回滚莫队。

对于左右端点在同一块中的询问，暴力处理。

对于左右端点不在同一块的询问，维护方法如下。

首先不进行奇偶化排序，按普通莫队朴素排序排，这样能保证右端点单调不减。

左端点在同一块内的询问，便可以这样操作：

右端点一开始在当前块的块尾，每次询问时不还原，不断向右拓展右端点。

左边块内没更新到的位置，就对于每个询问，暴力更新，然后清除。

而当两个询问的左端点不在同一块内时，便清空之前的询问所造成的影响，然后处理下一个块的询问。

由于值域很大，所以要离散化。

时间复杂度证明

共有 O(\sqrt{n}) 个块，每个块内的询问最坏时间复杂度是 O(n) 的（指针最坏情况下移动 O(n) 次），相乘得出时间复杂度为 O(n\sqrt{n})。

\color{#009a00}\texttt{Accepted} \texttt{Code}

/*我们所可以自慰的，想来想去，也还是所谓对于将来的希望。

希望是附丽于存在的，有存在，便有希望，有希望，便是光明。*/
#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e5+4;
int a[N],inv[N],pos[N],cnt[N],ans[N],now,tmp,n,b,k,tot=0;
map<int,int> mp;
struct query{
    int l,r,id;
    query()=default;
    query(int l,int r,int id):l(l),r(r),id(id){}
};
vector<query> Q;
inline void add(int p,int& t){
    ++cnt[a[p]];
    if(cnt[t]<cnt[a[p]]||(a[p]<t&&cnt[t]==cnt[a[p]])) t=a[p];
    return;
}
inline void del(int p){return --cnt[a[p]],void();} 
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;b=sqrt(n),k=(n+b-1)/b;
    for(int i=1;i<=n;++i) cin>>a[i],mp[a[i]],pos[i]=(i+b-1)/b;
    for(auto& i:mp) inv[i.second=++tot]=i.first;
    for(int i=1;i<=n;++i) a[i]=mp[a[i]];
    for(int i=0,l,r;i<n;Q.emplace_back(l,r,++i)) cin>>l>>r;
    stable_sort(Q.begin(),Q.end(),[](const query& x,const query& y)->bool{
        return (pos[x.l]^pos[y.l])? (pos[x.l]<pos[y.l]):(x.r<y.r);
    });
    for(int i=1,j=0,p=0,r;i<=k&&j<n;++i,tmp=now=n+1){
        for(;j<n&&pos[Q[j].l]==pos[Q[j].r];++j,now=n+1){
            for(p=Q[j].l;p<=Q[j].r;++p) add(p,now);
            ans[Q[j].id]=inv[now];
            for(p=Q[j].l;p<=Q[j].r;++p) del(p);
        }
        p=r=min(i*b,n),now=n+1;
        for(;j<n&&pos[Q[j].l]==i;++j,tmp=n+1){
            while(p<Q[j].r) add(++p,now);
            tmp=now;
            for(int t=Q[j].l;t<=r;++t) add(t,tmp);
            ans[Q[j].id]=inv[tmp];
            for(int t=Q[j].l;t<=r;++t) del(t);
        }
        while(r<p) del(++r);
    }
    for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
    return 0;
}