题解：P13984 数列分块入门 9

· · 题解

写一个 O(n\sqrt{n}) 的做法。

由于这是分块入门题，首先考虑朴素分块，感觉较为困难。但我们发现本题和 这题 有类似之处，于是我们考虑莫队套值域分块。

我们记录每种数在当前区间出现次数，并对值域分块，对于每个块处理出块内最大出现次数。询问时只需要从小到大每个块扫一遍确定答案在哪个块内，再在该块内扫一遍得到答案，询问总复杂度 O(n\sqrt{n})。

于是我们只需考虑如何处理块内最大出现次数。这里有两种处理方式。

第一种：我们注意到若是只有添加操作是容易的，因为答案单调不降。故可以使用回滚莫队，细节不多叙述。

第二种：我们考虑如何刻画删除操作。注意到只会对一种数的出现次数减一，故我们只需记每个块内各出现次数出现了多少次。若发现删除后最大出现次数的出现次数为零，则说明最大出现次数需减一。

两种方法均做到了 O(1)-O(\sqrt{n}) 的复杂度，结合莫队的复杂度，总时间复杂度为 O(n\sqrt{n})。注意值域较大，需要离散化。

这里给出第二种方法的实现。

#include<bits/stdc++.h>
#define int long long
#define gc getchar
//char buf[1<<20],*p1,*p2;
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define R read()
using namespace std;
int read()
{
    int x=0,f=1;
    char c=gc();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=gc();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=gc();
    return x*f;
}
void write(int x,char xx)
{
    static int st[35],top=0;
    if(x<0){x=-x;putchar('-');}
    do
    {
        st[top++]=x%10,x/=10;
    }while(x);
    while(top) putchar(st[--top]+48);
    putchar(xx);
}
#define N 300010
#define B 610
int n,a[N],S,ans[N],T,bid[N],po[N],b[N];
int bcnt[B],mx[B],cntb,cnt[N],stb[N],enb[N],pm[B][N];
unordered_map<int,int>mp;
struct node{int l,r,id;}que[N];
int cl(int x){return (x+S-1)/S;}
bool cmp(node x,node y){return (cl(x.l)==cl(y.l))?(cl(x.l)&1?x.r>y.r:x.r<y.r):x.l<y.l;}
void add(int x)
{
    x=a[x],pm[bid[x]][cnt[x]]--,cnt[x]++,pm[bid[x]][cnt[x]]++;
    if(cnt[x]>mx[bid[x]]) mx[bid[x]]=cnt[x];
}
void del(int x)
{
    x=a[x],pm[bid[x]][cnt[x]]--,cnt[x]--,pm[bid[x]][cnt[x]]++;
    if(!pm[bid[x]][mx[bid[x]]]) mx[bid[x]]--;
}
int qu()
{
    int id=1;
    for(int i=2;i<=cntb;i++) if(mx[i]>mx[id]) id=i;
    for(int i=stb[id];i<=enb[id];i++) if(cnt[i]==mx[id]) return b[i];
}
signed main()
{
    n=R,S=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=b[i]=R;
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    for(int i=1;i<=n;i++) que[i]={R,R,i},bid[i]=cl(i),(bid[i]==bid[i-1]?0:stb[bid[i]]=i,enb[bid[i-1]]=i-1);
    cntb=bid[n];
    sort(que+1,que+n+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        while(l>que[i].l) add(--l);
        while(r<que[i].r) add(++r);
        while(l<que[i].l) del(l++);
        while(r>que[i].r) del(r--);
        ans[que[i].id]=qu();
    }
    for(int i=1;i<=n;i++) write(ans[i],'\n');
    return 0;
}