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
不说了,直接%%%