数据结构 分块 P3709题解

· · 题解

题目大意

简化后为区间众数出现次数，简化前为【数据删除】

吐槽

为什么题解只有一篇分块，剩下的全是莫队？

这题不是蒲公英？这和算导例题有何区别？？？

为什么现在的人都喜欢去看题解而不注重思维？？？

莫队之前也胡过区间众数莫队，由于太菜胡出来了一个回滚莫队。（毕竟暴力思路这题很难删）

题解

因为某些原因代码是从 P5048 搬过来然后把强制在线去掉后加了个负号（

首先我们对序列分块，然后求出左右端点同时也是某个块的左右端点的区间的众数出现次数。（语文差轻喷）

然后对于一个询问，把询问区间分为整块和边角块后，我们很容易能够知道答案一定在 O(整块答案) 级别。所以我们枚举边角块的 O(\sqrt n) 个数，看它在区间中出现了多少次就行了。

但是数出现次数的方法有点儿妙。

我们开 n 个 vector 记录每一种数出现的下标。

假如一个边角块的数可能成为答案（设其为 k ），那么这个数后面的第整块答案个 k 一定也在区间内。

而很容易知道更新答案的复杂度是 O(\sqrt n) 的。

code:

#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
const int N=805,M=5e5+5;
int n,m,p,ans,siz,len,a[M],t[M],pre[M],cnt[M],lsh[M],ANS[N][N];
int L[N],R[N],pos[M];
bool vis[M];
std::vector<int>id[M];
inline int min(const int&a,const int&b){
    return a>b?b:a;
}
inline int Query(int l,int r){
    int i,j,q=pos[l],p=pos[r];
    if(q+1>=p||q==p){
        for(i=l;i<=r;++i){
            if(++cnt[a[i]]>ans)ans=cnt[a[i]];
        }
        for(i=l;i<=r;++i)--cnt[a[i]];
        return ans;
    }
    ans=ANS[q+1][p-1];
    for(i=l;i<=R[q];++i){
        for(j=pre[i]+ans;j<id[a[i]].size()&&id[a[i]][j]<=r;++j)++ans;
    }
    for(i=L[p];i<=r;++i){
        for(j=pre[i]-ans;j>=0&&id[a[i]][j]>=l;--j)++ans;
    }
    return ans;
}
signed main(){
    register int i,j,k,x=0,ql,qr;
    scanf("%d%d",&n,&m);p=ceil(n/sqrt(m));
    for(i=1;i<=n;++i){
        scanf("%d",a+i);lsh[i]=a[i];
        pos[i]=(i-1)/p+1;
    }
    siz=pos[n];
    for(i=1;i<=siz;++i)L[i]=R[i-1]+1,R[i]=i*p;
    R[siz]=n;
    std::sort(lsh+1,lsh+n+1);len=std::unique(lsh+1,lsh+n+1)-lsh-1;
    for(i=1;i<=n;++i){
        a[i]=std::lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
        id[a[i]].push_back(i);pre[i]=id[a[i]].size()-1;
    }
    for(i=1;i<=siz;++i){
        for(j=i;j<=siz;++j){
            for(k=L[j];k<=R[j];++k){
                if(++cnt[a[k]]>ans)ans=cnt[a[k]];
            }
            ANS[i][j]=ans;
        }
        for(j=L[i];j<=n;++j)--cnt[a[j]];ans=0;
    }
    for(i=1;i<=m;++i){
        scanf("%d%d",&ql,&qr);ans=len=0;
        printf("%d\n",-Query(ql,qr));
    }
}