正题

题目链接:https://www.luogu.com.cn/problem/P5048

题目大意

就是这个

【QA】区间众数，但空间很小

长度为\(n\)的序列，要求支持查找区间众数出现次数。

强制在线

\(1\leq n,m\leq 5\times 10^5\)

解题思路

空间小就不能用蒲公英那种做法了

分块然后处理出每个连续块段的众数，就是设\(f_{l,r}\)表示从块\(l\sim r\)的区间众数出现次数。

然后考虑散块的部分，如果散块会更新答案那么显然新的众数一定是出现在散块里的，所以答案增加不会超过\(2\sqrt n\)

用\(vector\)记录每个数字出现的位置，然后对于散块的每个数字我们看一下\(ans\)能否增加（就是往下到第\(ans+1\)个数字是否还在范围内就好了）

时间复杂度\(O(n\sqrt n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

const int N=5e5+10,M=710;

int n,m,cnt,pos[N],a[N],b[N],c[N],w[N],L[M],R[M],f[M][M];

vector<int>v[N];

int Ask(int l,int r){

	int q=pos[l],p=pos[r];

	if(q==p){

		int ans=0;

		for(int i=l;i<=r;i++)

			++c[a[i]],ans=max(ans,c[a[i]]);

		for(int i=l;i<=r;i++)c[a[i]]=0;

		return ans;

	}

	int ans=f[q+1][p-1];

	for(int i=l;i<=R[q];i++)

		while(w[i]+ans<v[a[i]].size()&&v[a[i]][w[i]+ans]<=r)ans++;

	for(int i=L[p];i<=r;i++)

		while(w[i]-ans>=0&&v[a[i]][w[i]-ans]>=l)ans++;

	return ans;

}

int main()

{

	scanf("%d%d",&n,&m);

	int T=sqrt(n);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]),b[i]=a[i];

	sort(b+1,b+1+n);

	int mnt=unique(b+1,b+1+n)-b-1;

	for(int i=1;i<=n;i++){

		a[i]=lower_bound(b+1,b+1+mnt,a[i])-b;

		v[a[i]].push_back(i);

		w[i]=v[a[i]].size()-1;

	}

	for(int i=1;i*T<=n;i++)

		++cnt,L[cnt]=R[cnt-1]+1,R[cnt]=i*T;

	if(R[cnt]<n)++cnt,L[cnt]=R[cnt-1]+1,R[cnt]=n;

	for(int i=1;i<=cnt;i++)

		for(int j=L[i];j<=R[i];j++)pos[j]=i;

	for(int i=1;i<=cnt;i++){

		for(int j=i;j<=cnt;j++){

			f[i][j]=f[i][j-1];

			for(int k=L[j];k<=R[j];k++)

				++c[a[k]],f[i][j]=max(f[i][j],c[a[k]]);

		}

		for(int k=L[i];k<=n;k++)c[a[k]]=0;

	}

	int last=0;

	while(m--){

		int l,r;

		scanf("%d%d",&l,&r);

		l^=last;r^=last;

		printf("%d\n",last=Ask(l,r));

	}

	return 0;

}

巴特西

P5048-[Ynoi2019 模拟赛]Yuno loves sqrt technology III【分块】

正题

题目大意

解题思路

code

最新文章

热门文章