自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:06:33，当前版本为作者最后更新于2018-11-21 18:12:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人题解

众所周知lxl是个毒瘤，Ynoi道道都是神仙题

首先得离散化。

分块后，预处理$F_{i,j}$表示第$i\sim j$块的众数的出现次数。此处要用一个桶，空间复杂度$O(n)$，时间复杂度$O(n\sqrt n)$。

用vector按顺序存每个数值所有元素的出现位置。

再记录每个元素在相应vector里的下标$p$。

以上空间复杂度都是$O(n)$的。

考虑询问，中间的直接使用预处理出的$F_{i,j}$的值即可。设当前的答案$ans=F_{i,j}$。

考虑边界的元素。

显然，由于边界的数最多$2\sqrt n$个，所以最多使得答案增加$2\sqrt n$。

我们只需要检查这些边角的元素，每次判断这些数的出现次数能否达到$ans+1$。

对于左边的边角元素$x$，我们在相应的vector里找到下标为$p_x+ans$的元素$y$，若$y\leqslant r$，则说明该数值在范围内有至少$ans+1$个数，暴力++ans即可。

对于右边的边角元素$x$，我们在相应的vector里找到下标为$p_x-ans$的元素$y$，若$y\geqslant l$，则说明该数值在范围内有至少$ans+1$个数，暴力++ans即可。

每次询问对$O(\sqrt n)$个元素检查，++ans的次数为$O(\sqrt n)$次。所以查询的时间复杂度为$O(m\sqrt n)$。

总时间复杂度$O((n+m)\sqrt n)$，空间复杂度$O(n)$。

Code：

#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#define siz 708
#define N 500001
class istream{
	char buf[20000003],*s;
	public:
		inline istream(){
#ifndef ONLINE_JUDGE
			freopen("input.txt","r",stdin);
#endif
			fread(s=buf,1,20000003,stdin);
			fclose(stdin);
		}
		inline istream&operator>>(int&rhs){
			int f=rhs=0;
			for(;!isdigit(*s);++s)f=*s=='-';
			for(;isdigit(*s);)
			rhs=(rhs<<3)+(rhs<<1)+(*s++^'0');
			if(f)rhs=-rhs;
			return*this;
		}
}cin;
class ostream{
	char buf[5000005],*s;
	public:
		inline ostream(){s=buf;}
		inline ostream&operator<<(int rhs){
			if(rhs<0)*s++='-',rhs=-rhs;
			if(rhs==0){
				*s++='0';
				return*this;
			}
			static int w;
			for(w=1;w<=rhs;w*=10);
			for(w/=10;w;w/=10)*s++=(rhs/w)^'0',rhs%=w;
			return*this;
		}
		inline ostream&operator<<(const char&rhs){*s++=rhs;return*this;}
		inline~ostream(){
			fwrite(buf,1,s-buf,stdout);
		}
}cout;
int n,m,L[710],R[710],bel[N],blocks,mx[710][710],ans,tot[N],wz[N],a[N];
void init(){
	blocks=(n-1)/siz+1;
	for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*siz;
	R[blocks]=n;
	for(int i=1;i<=blocks;++i){
		memset(tot,0,sizeof tot);
		for(int j=L[i];j<=R[i];++j)bel[j]=i;
		for(int j=i;j<=blocks;++j){
			int&F=mx[i][j];
			F=mx[i][j-1];
			for(int k=L[j];k<=R[j];++k)
			F=std::max(F,++tot[a[k]]);
		}
	}
}
std::vector<int>ls,v[N];
int main(){
	ls.push_back(-1);
	cin>>n>>m;
	for(int i=1;i<=n;ls.push_back(a[i++]))cin>>a[i];
	std::sort(ls.begin(),ls.end());
	ls.erase(std::unique(ls.begin(),ls.end()),ls.end());
	for(int i=1;i<=n;++i)v[a[i]=std::lower_bound(ls.begin(),ls.end(),a[i])-ls.begin()].push_back(i),wz[i]=v[a[i]].size()-1;
	init();
	memset(tot,0,sizeof tot);
	while(m--){
		int l,r;cin>>l>>r;
		l^=ans,r^=ans;
		ans=0;
		if(bel[l]==bel[r]){
			for(int i=l;i<=r;++i)ans=std::max(ans,++tot[a[i]]);
			for(int i=l;i<=r;++i)tot[a[i]]=0;
		}else{
			ans=mx[bel[l]+1][bel[r]-1];
			for(int i=l;i<=R[bel[l]];++i){
				int it=wz[i];
				while(it+ans<v[a[i]].size()&&v[a[i]][it+ans]<=r)++ans;
			}
			for(int i=L[bel[r]];i<=r;++i){
				int it=wz[i];
				while(it-ans>=0&&v[a[i]][it-ans]>=l)++ans;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}