P5048 [Ynoi2019 模拟赛] 题解

题意

给定 \(n\) 个数，有 \(m\) 个询问，每个询问给定 \(l\) 和 \(r\)，求出区间 \(l\) 到 \(r\) 中的最小众数出现次数，强制在线。

数据范围：\(n\le 500000\)，空间限制：\(62.5MB\)。

思路

这道题的弱化版是 蒲公英，这道题加强的地方在于数据范围。正常的分块求区间众数的空间复杂度是 \(O(n\sqrt n)\) 的，这道题显然会 \(MLE\)，于是考虑优化空间。

我们可以记录一个 \(vector\) 数组 \(v_{i}\) 表示值为 \(i\) 的所有数分别在原数组中的下标是多少，升序排列。再记录一个 \(s_{i}\) 表示在原数组中下标为 \(i\) 的数在它对应的 \(v_{s_{i}}\) 中的位置。在查询的时候先将 \(ans\) 赋值为中间所有整块的众数出现次数，再暴力枚举非整块。对于每一个数只需要判断当前数能否在 \(l\) 到 \(r\) 中出现 \(ans+1\) 次，即 \(a_{i}\) 在原数组出现 \(s_{i}\pm ans\) 次时是否小于 \(r\) 或者大于 \(l\)，如果满足条件的话答案加一。

Code

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 2e5 + 1,MAXM = 5e2 + 1;
int n,m,len,num,t[MAXN],c,nowans,s[MAXN];
int p[MAXM][MAXM],a[MAXN],tmp[MAXN],l,r,lastans;
vector <int> v[MAXN];
inline bool cmp(int x,int y){return x < y;}
inline int Getpos(int x){return (x % len ? x / len + 1 : x / len);}
inline int Getlid(int x){return (x - 1) * len + 1;}
inline int Getrid(int x){return min(n,x * len);}
inline void Init()
{
	for(re int i = 1;i <= n;++i) tmp[i] = a[i];
	sort(tmp + 1,tmp + n + 1,cmp);
	c = unique(tmp + 1,tmp + n + 1) - tmp - 1;
	for(re int i = 1;i <= n;++i) a[i] = lower_bound(tmp + 1,tmp + c + 1,a[i]) - tmp;
	for(re int i = 1;i <= n;++i) v[a[i]].push_back(i),s[i] = v[a[i]].size() - 1;
	len = sqrt(n);num = ceil(1.0 * n / len);
	for(re int i = 1;i <= num;++i)
	{
		for(re int j = 1;j <= c;j++) t[j] = 0;
		nowans = 0;
		for(re int j = i;j <= num;++j)
			for(re int k = Getlid(j);k <= Getrid(j);++k)
			{
				t[a[k]]++;
				if(t[a[k]] > t[nowans]) nowans = a[k];
				if(t[a[k]] == t[nowans] && a[k] < nowans) nowans = a[k];
				p[i][j] = t[nowans];
			}
	}
}
inline int Ask(int l,int r)
{
	nowans = 0;
	int ct = 0,L = Getpos(l),R = Getpos(r);
	int Lid = Getlid(R),Rid = Getrid(L);
	if(L == R)
	{
		for(re int i = l;i <= r;++i) t[a[i]] = 0;
		for(re int i = l;i <= r;++i)
		{
			t[a[i]]++;
			if(a[i] == nowans) ct++;
			if(t[a[i]] > t[nowans]) nowans = a[i],ct = t[nowans];
			if(t[a[i]] == t[nowans] && a[i] < nowans) nowans = a[i],ct = t[nowans];
		}
		return t[nowans];
	}
	nowans = p[L + 1][R - 1];
	for(re int i = l;i <= Rid;++i) 
	{
		int length = v[a[i]].size();
		while(nowans + s[i] < length && v[a[i]][nowans + s[i]] <= r) nowans++;
	}
	for(re int i = Lid;i <= r;++i) while(s[i] - nowans >= 0 && v[a[i]][s[i] - nowans] >= l) nowans++;
	return nowans;
}
signed main()
{
	scanf("%d%d",&n,&m);
	for(re int i = 1;i <= n;++i) scanf("%d",&a[i]);
	Init();
	for(re int i = 1;i <= m;++i) 
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",-Ask(l,r));
	}
	return 0;
}