题解：P13984 数列分块入门 9

前言

~~洛谷终于有分块模板啦！~~

思路

由于众数不满足“区间可加性”，因此难以用线段树或者树状数组进行维护，所以考虑分块。

先考虑整块。用

m_{i,j}

表示第

i

块到第

j

块的区间众数。枚举左块，然后向右拓展每一个数，然后看一下当前拓展的数出现次数是否为最大的，如果是，则更新左块到当前拓展的数所在块的答案。复杂度

O(n\sqrt n)

。

此时的众数可能来自三个地方：左边散块，中间整块，右边散块。中间很好搞，上一段已预处理，散块呢？考虑到散块大小不超过

\sqrt n

，所以我完全可以暴力算散块中每个数在整个区间的出现次数，最后三个地方取最大值即可。复杂度

O(\sqrt n)

。

最后不要忘了离散化。

代码

CPP

#include<bits/stdc++.h>//代码有些丑陋
using namespace std;
const int N=3e5+5;
int a[N],sum[1001][N],m[1001][1001],cnt[N];
int pos[N],b[N],L[1001],R[1001];
int n;
int len;
void init()
{
	int t=sqrt(n);
	for(int i=1;i<=t;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=i*t;
	}
	if(R[t]<n)
	{
		t++;
		R[t]=n;
		L[t]=R[t-1]+1;
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=1;j<=len;j++) sum[i][j]=sum[i-1][j];//表示前i块j出现次数，以便后面查询p到q块某个数出现次数
		for(int j=L[i];j<=R[i];j++)
		{
			sum[i][a[j]]++;
		}
	}
	for(int i=1;i<=t;i++)
	{
		int res=0,ans=0;
		for(int j=L[i];j<=n;j++)
		{			
			cnt[a[j]]++;
			if(cnt[a[j]]>res||(cnt[a[j]]==res&&b[a[j]]<b[ans]))//按题意取最值
			{
				res=cnt[a[j]];
				ans=a[j];
			}
			m[i][pos[j]]=ans;
		}
		memset(cnt,0,sizeof cnt);
	}	
}
int enquir(int l,int r)
{
	int t=sqrt(n);
	int p=pos[l],q=pos[r];
	int ans=m[p+1][q-1],res=max(0,sum[q-1][ans]-sum[p][ans]);
	int lim=min(R[p],r),f=0;
	if(p!=q) f=1;\\代表中间有整块
	for(int i=l;i<=lim;i++) cnt[a[i]]=max(0,sum[q-1][a[i]]-sum[p][a[i]]);
	if(f)
	{
		for(int i=L[q];i<=r;i++)
		{
			cnt[a[i]]=max(0,sum[q-1][a[i]]-sum[p][a[i]]);
		}
	}
	for(int i=l;i<=lim;i++)
	{
		cnt[a[i]]++;
		if(cnt[a[i]]>res||(cnt[a[i]]==res&&b[a[i]]<b[ans]))
		{
			ans=a[i];
			res=cnt[a[i]];
		}
	}
	if(f)
	{
		for(int i=L[q];i<=r;i++)
		{
			cnt[a[i]]++;
			if(cnt[a[i]]>res||(cnt[a[i]]==res&&b[a[i]]<b[ans]))
			{
				ans=a[i];
				res=cnt[a[i]];
			}
		}
	}
	return ans;
}
signed main()
{
//	freopen("P4168_3.in","r",stdin);
//	freopen("P4168_3.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	init();
	int l,r,x=0;
	for(int i=1;i<=n;i++)
	{
		cin>>l>>r;
		if(l>r) swap(l,r);
		x=b[enquir(l,r)];
		cout<<x<<endl;
	}
	return 0;
}

题解：P13984 数列分块入门 9

文章操作

前言

思路

代码

相关推荐

评论

题解：P13984 数列分块入门 9