您的位置: 首页  >  IT文章  >  蒲公英（洛谷4168分块）

蒲公英（洛谷4168分块）

分类: IT文章 • 2022-08-10 14:11:31

传送门

这道题其实就是询问区间众数且强制在线。

若题目是询问区间是否有过半众数，就是主席树，按值域建树，不断判断左右子树子节点数量大于（r-l+1）/2，如果一直可以到叶子节点，则return true，否则return false

若题目是询问区间是否有过半众数且带修改，就是树套树（虽然我还没打过树套树）

若题目是询问区间众数且可以离线，就可以用莫队做，信息只增不删，开一个桶（离散化）维护各数出现次数，时间O（n√n）
然鹅，这道题是询问区间众数且强制在线。

那我们可以考虑分块做法，n<=40000，是符合O（n√n）的

思考：对于一个区间，这个区间存在两种情况

1.[L，R]都由整块构成

2.[L，R]由整块和一些零散的点构成

我们可以预处理出这样的两个数组

sum[i][j]从最开始到第i块j这种颜色出现的次数，p[i][j]第i块到第j块的众数

处理p数组时有一个小技巧，保证时间

我原来的处理是这样的

for(int i=1;i<=num;++i)
      for(int j=i;j<=num;++j)
      {
           int tot=0,col=INF;
           for(int k=1;k<=n;++k)
           {
              if(sum[j][k]-sum[i-1][k]>tot||(sum[j][k]-sum[i-1][k]==tot&&k<col))
                tot=sum[j][k]-sum[i-1][k],col=k;
         }
         p[i][j]=col;
      }
TLE

会T

然后我们可以这样打

for(int i=1;i<=num;++i)
    {
        int tot=0,col=INF;
        for(int j=l[i];j<=n;++j)
        {
            int pos=id[j];
            tong[a[j]]++;//开桶处理p数组
            if(tong[a[j]]>tot||(tong[a[j]]==tot&&col>a[j]))
               tot=tong[a[j]],col=a[j];
            p[i][pos]=col;
        }
        for(int j=l[i];j<=n;++j)tong[a[j]]=0;
    }
right

每一次在统计的时候，先找到整块的众数，前后的残余的点开一个桶暴力判断即可（每一次桶记得清空）

记得离散化

代码~

#include<bits/stdc++.h>
#define INF 2100000001
#define N 40003
#define LL long long
using namespace std;
int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
//sum[i][j]从最开始到第i块j这种颜色出现的次数，p[i][j]第i块到第j块的众数，id[i]i所在的块
int n,m,num,pp; 
int a[N],b[N],l[202],r[202],id[N],color[N],tong[N],ans[50003];
int ge[202][202],p[202][202],sum[202][N];
void init()
{
    int base=sqrt(1.0*n);
    for(int i=1;i*base<n;++i)
    {
        int tot=0,col=INF;
        l[i]=base*(i-1)+1;
        r[i]=base*i;
        for(int j=l[i];j<=r[i];++j)
        {
            id[j]=i;
            sum[i][a[j]]++;//在第i块a[j]颜色的个数 
        }     
        num=i;
    }
    num++;
    l[num]=base*(num-1)+1;r[num]=n;
    for(int j=l[num];j<=r[num];++j)id[j]=num,sum[num][a[j]]++;//单纯分块，最后一块单独处理
    for(int i=1;i<=num;++i)
      for(int j=1;j<=pp;++j)
        sum[i][j]+=sum[i-1][j];//前缀和处理sum
    for(int i=1;i<=num;++i)
    {
        int tot=0,col=INF;
        for(int j=l[i];j<=n;++j)
        {
            int pos=id[j];
            tong[a[j]]++;//开桶处理p数组
            if(tong[a[j]]>tot||(tong[a[j]]==tot&&col>a[j]))
               tot=tong[a[j]],col=a[j];
            p[i][pos]=col;
        }
        for(int j=l[i];j<=n;++j)tong[a[j]]=0;
    } 
}
int query(int L,int R)
{
    memset(tong,0,sizeof(tong));
    int pos1=id[L],pos2=id[R];
    if(pos2-pos1<=1)//两块及以下暴力处理
    {
        int answer=INF,tot=0;
        for(int i=L;i<=R;++i)
        {
            ++tong[a[i]];
            if(tong[a[i]]>tot||(tong[a[i]]==tot&&answer>a[i]))
              tot=tong[a[i]],answer=a[i];
        }
        return answer;
    }
    int answer=p[pos1+1][pos2-1];//先取出整块的众数
    int tot=sum[pos2-1][answer]-sum[pos1][answer];
    int x=L,y=l[pos1+1]-1;//前面残余的
    for(int i=x;i<=y;++i)
    {
        ++tong[a[i]];
        if(tong[a[i]]+sum[pos2-1][a[i]]-sum[pos1][a[i]]>tot||(tong[a[i]]+sum[pos2-1][a[i]]-sum[pos1][a[i]]==tot&&answer>a[i]))
          tot=tong[a[i]]+sum[pos2-1][a[i]]-sum[pos1][a[i]],answer=a[i];
    }
    x=l[pos2],y=R;//后面残余的
    for(int i=x;i<=y;++i)
    {
        ++tong[a[i]];
        if(tong[a[i]]+sum[pos2-1][a[i]]-sum[pos1][a[i]]>tot||(tong[a[i]]+sum[pos2-1][a[i]]-sum[pos1][a[i]]==tot&&answer>a[i]))
          tot=tong[a[i]]+sum[pos2-1][a[i]]-sum[pos1][a[i]],answer=a[i];
    }
    return answer;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=b[i]=read();
    sort(b+1,b+1+n);
    pp=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;++i)
    {
        int col=a[i];
        a[i]=lower_bound(b+1,b+1+pp,a[i])-b;
        color[a[i]]=col;//离散化
    }
    init();
    for(int i=1;i<=m;++i)
    {
        int L=read(),R=read();
        int x=(L+ans[i-1]-1)%n+1;
        int y=(R+ans[i-1]-1)%n+1;
        if(x>y)swap(x,y);
        ans[i]=color[query(x,y)];
        printf("%d
",ans[i]);
    }
}
蒲公英

相关推荐