【题解】蒲公英

题目链接

前置知识:分块

解题思路

本题是一道计算区间出现次数最多的数字的题目。

如果我们想用主席树做会发现时间复杂度和暴力没有什么不同,甚至还慢一点。

这时我们可以想到另一种维护区间的思想:分块。

我们可以用一个dT[N]记录下每个块组成的连续块段中每个数字的个数。

对于每一次询问暴力在di[N]上加上最左边和最右边不在块内的两端即可。

于是你可能写出这样的代码:

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
    return ;

}
inline int read(){
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
int n,m;
int a[40005],li[40005];
int t;
int d[40][40][40005];
int len;
inline void init(){
    register int kk=n/t;
    for(int i=1;i<=n;i++){
        int pos=(i-1)/kk+1;
        d[pos][pos][a[i]]++;
    }
    for(register int i=1;i<=t;i++){
        for(register int j=i+1;j<=t;j++){
            for(register int k=1;k<=len;k++)d[i][j][k]=d[i][j-1][k]+d[j][j][k];
        }
    }
}
int ans=0,pos;
inline void query(int l,int r){
    register int k=n/t;
    register int ed=((l-1)/k+1)*k; 
    register int st=(r-1)/k*k+1;
    if(st<ed)st=99999999,ed=r;
    register int from=(l-1)/k+2,to=(r-1)/k;
    for(register int i=l;i<=ed;i++){
        d[from][to][a[i]]++;
    }
    for(register int i=st;i<=r;i++){
        d[from][to][a[i]]++;
    }
    for(register int i=1;i<=n;i++){//标记!!!
        if(ans<d[from][to][i]){
            ans=d[from][to][i],pos=i;
        }
    }
    write(li[pos]);
    putchar('\n');
    for(register int i=l;i<=ed;i++){
        d[from][to][a[i]]--;
    }
    for(register int i=st;i<=r;i++){
        d[from][to][a[i]]--;
    } 
}
void lisan(){
    sort(li+1,li+1+n);
    len=unique(li+1,li+1+n)-li-1;
    for(register int i=1;i<=n;i++){
        a[i]=lower_bound(li+1,li+len+1,a[i])-li;
    }
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();
        li[i]=a[i];
    }
    lisan();
    t=pow(n,1.0/3);
    init();
    register int l,r;
    for(register int i=1;i<=m;i++){
        l=read(),r=read();
        l=(l+li[pos]-1)%n+1,r=(r+li[pos]-1)%n+1;
        if(l>r)swap(l,r);
        ans=0;
        query(l,r);
    }
    return 0;
}

在我打标记的地方是否看出一些不妥?

是的,query如果有一个O(n)的循环,则n*m=2e9直接炸。

但是很容易发现,里面有一些可以不考虑,所以我们要先预处理出区间最多出现的数以及它出现的次数,然后在query中每一次加上左右端的数时判断一下是不是有数字出现次数比最大的次数大。

这样就很容易地将O(n)缩小为O(n/t)了。

关于复杂度

可以看出整个算法的时间为 $O(NT^2+MN/T)$ ,空间复杂度为 $O(NT^2)$

我们将M和N看做同一大小,则复杂度约为 $O(NT^2+N^2/T)$

通过均值不等式可得 $NT^2+N^2/T\ge 2\sqrt{TN^3}$ ,不等式成立当且仅当 $NT^2=N^2/T$ 。

所以 $N=T^3$ ,T取 $N^{\frac{1}{3}}$

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
    return ;

}
inline int read(){
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}

int n,m;
int a[40005],li[40005];
int t;
int d[40][40][40005];
int cntmax[40][40];
int maxpos[40][40];
int len;


inline void init(){
    register int kk=n/t;
    register int pos;
    for(int i=1;i<=n;i++){
        pos=(i-1)/kk+1;
        d[pos][pos][a[i]]++;
        if(cntmax[pos][pos]<d[pos][pos][a[i]]||(cntmax[pos][pos]==d[pos][pos][a[i]]&&maxpos[pos][pos]>a[i])){
            cntmax[pos][pos]=d[pos][pos][a[i]];
            maxpos[pos][pos]=a[i];
        }
    }
    for(register int i=1;i<=t;i++){
        for(register int j=i+1;j<=t;j++){
            for(register int k=1;k<=len;k++){
                d[i][j][k]=d[i][j-1][k]+d[j][j][k];
                if(cntmax[i][j]<d[i][j][k]||(cntmax[i][j]==d[i][j][k]&&maxpos[i][j]>k)){
                    cntmax[i][j]=d[i][j][k];
                    maxpos[i][j]=k;
                }
            }
        }
    }
}
int ans=0,pos;
inline void query(int l,int r){//O(n^(2/3)*4)
    register int k=n/t;//每一段的长度 
    register int ed=((l-1)/k+1)*k;
    register int st=(r-1)/k*k+1; 
    if(st<ed)st=99999999,ed=r;
    register int from=(l-1)/k+2,to=(r-1)/k;
    pos=maxpos[from][to];
    ans=cntmax[from][to];
    for(register int i=l;i<=ed;i++){ 
        d[from][to][a[i]]++;
        if(ans<d[from][to][a[i]]||(ans==d[from][to][a[i]]&&pos>a[i])){
            ans=d[from][to][a[i]];
            pos=a[i];
        }
    }
    for(register int i=st;i<=r;i++){//O(n^2/3)
        d[from][to][a[i]]++;
        if(ans<d[from][to][a[i]]||(ans==d[from][to][a[i]]&&pos>a[i])){
            ans=d[from][to][a[i]];
            pos=a[i];
        }
    }
    write(li[pos]);
    putchar('\n');
    for(register int i=l;i<=ed;i++){
        d[from][to][a[i]]--;
    }
    for(register int i=st;i<=r;i++){
        d[from][to][a[i]]--;
    } 
}
void lisan(){
    sort(li+1,li+1+n);
    len=unique(li+1,li+1+n)-li-1;
    for(register int i=1;i<=n;i++){
        a[i]=lower_bound(li+1,li+len+1,a[i])-li;
    }
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();
        li[i]=a[i];
    }
    lisan();
    t=pow(n,1.0/3);
    init();
    register int l,r;
    for(register int i=1;i<=m;i++){
        l=read(),r=read();
        l=(l+li[pos]-1)%n+1,r=(r+li[pos]-1)%n+1;
        if(l>r)swap(l,r);
        ans=0;
        query(l,r);
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/673/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者