大佬留步

P4168 [Violet] 蒲公英

7KByte @ 2019-03-10 16:29:54

为什么我的分块跑不过暴力?!
求大佬支招


#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[40005],len;
int ans[60][60],Max[60][60],cnt[60][60][40001];
int L[50],R[50],pos[40005]; 
map<int,int>f;int pop=0,to[40001],F[40001];
int val[40005];
int ask(int l,int r){
    int x=pos[l],y=pos[r];
    if(y-x<=1){
        int Ans=0,MAX=0;
        for(int i=l;i<=r;i++){
            int T=++val[F[i]];
            if(T==MAX&&Ans>a[i])Ans=a[i];
            else if(T>MAX)Ans=a[i],MAX=T;
        }
        for(int i=l;i<=r;i++)
          val[F[i]]--;
        return Ans;
    }
    int Ans=ans[x+1][y-1],MAX=Max[x+1][y-1];
    for(int i=l;i<=R[x];i++){
        int T=++cnt[x+1][y-1][F[i]];
        if(T==MAX&&Ans>a[i])Ans=a[i];
        else if(T>MAX)MAX=T,Ans=a[i];
    }
    for(int i=L[y];i<=r;i++){
        int T=++cnt[x+1][y-1][F[i]];
        if(T==MAX&&Ans>a[i])Ans=a[i];
        else if(T>MAX)MAX=T,Ans=a[i];
    }
    for(int i=l;i<=R[x];i++)
      cnt[x+1][y-1][F[i]]--;
    for(int i=L[y];i<=r;i++)
      cnt[x+1][y-1][F[i]]--;
    return Ans;
}
int main()
{
    //freopen("testdata(7).in","r",stdin);
    //freopen("tt.out","w",stdout);
    //memset(ans,0,sizeof(ans));
    //memset(Max,0,sizeof(Max));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
      scanf("%d",&a[i]);
      if(f[a[i]])F[i]=f[a[i]];
      else F[i]=f[a[i]]=++pop;
    }
    t=pow(n*1.0,1.0/3);len=n/t;
    for(int i=1;i<=t;i++){
        L[i]=len*(i-1)+1;
        R[i]=len*i;
    }
    if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
    //freopen("tt.out","w",stdout);
    for(int i=1;i<=t;i++)
      for(int j=L[i];i<=R[i];i++)
        pos[j]=i;
    for(int i=1;i<=t;i++)
      for(int j=i;j<=t;j++){
        for(int k=L[i];k<=R[j];k++)
          {
            int y=++cnt[i][j][F[k]];
            if(y==Max[i][j]&&a[k]<ans[i][j])ans[i][j]=a[k];
            if(y>Max[i][j])ans[i][j]=a[k],Max[i][j]=y;
            }
    }
    int x=0,u,v;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        int l=(u+x-1)%n+1,r=(v+x-1)%n+1;
        if(l>r)swap(l,r);
        printf("%d\n",x=ask(l,r));
    }
    return 0;
}

by 142857cs @ 2019-03-10 16:39:30

因为你的分块就是暴力


by 142857cs @ 2019-03-10 16:41:49

cnt数组要用前缀和优化,然后块大小开到sqrt(n)


by Juan_feng @ 2019-03-10 16:42:17

你这分块是带log的吧qaq


by 142857cs @ 2019-03-10 16:44:04

或者你可以尝试一下lxl最近(好像有点久了)引入的算法,那个跑5e5问题都不是很大


by 吾王美如画 @ 2019-03-10 17:15:18

不说了,直接%%%


|