大佬留步
查看原帖
大佬留步
119261
7KByte楼主2019/3/10 16:29

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


#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;
}
2019/3/10 16:29
加载中...