Lutece 2158 我永远喜欢冬马和纱

题目链接: https://acm.uestc.edu.cn/problem/wo-yong-yuan-xi-huan-dong-ma-he-sha/description

分析:

这道题是一道莫队算法的题目

1.莫队算法的排序问题

这个是较简单的问题。如果只按照左端点或者右端点排序的话,就会出现类似(1,100),(2,3),(3,100)这样子的毒瘤数据把右端点移动的次数大大增加。

解决的方法就是分块排序。让询问在一定范围内看起来有有序。换句话说,牺牲左端点移动次数来换取右端点移动次数的大幅减小,或者相反。

块也不是真正意义上的块,只是简单地按照长度分而已。

2.数据离散化问题

数据范围太大,无法使用桶排序。

简单来说,就是将保存数值的数组转化为保存相对大小位置的数组。需要使用到值时,再去离散化的数组中找。

3.询问

由于使用了莫队算法,只要计算增加一个数和减少一个数的对答案的贡献即可。

按照我的理解,cnt[i]的值,就是从左端点到右端点这段序列中,i出现的次数。

而sum[i]的值,就是次数的次数。

增加时,首先要把sum–,因为此时i出现的次数发生变化,那么它次数的次数也会受到影响。接着cnt++,新的cnt对应的sum++。此时的最大值要么不变要么是增加后的cnt。

减少时,先sum–。然后检查最大值与改变的这个值是不是同一个,如果不是,最大值就不变;如果是,就要检查这个最大值对应的sum还有没有别的数,有就不用变,没有就要跟着-1。最后处理cnt和sum。

输出时注意按照原来的顺序输出即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int v[MAXN];
int lsh_v[MAXN];
int ans[MAXN];
int sum[MAXN];
int cnt[MAXN];
int n, m, l, r, len, nowl = 1, nowr = 0, lsh_len, res=0, x;
struct query
{
	int L, R, ID,block;
	query() {}
	query(int _L, int _R, int _ID)
	{
		L = _L; R = _R; ID = _ID;
		block = l / len;
	}
	bool operator < (const query &a) const
	{
		if (block == a. block)
		{
			return R < a.R;
		}
		return block < a.block;
	}
}q[MAXN];
void add(int pos)
{
	x = v[pos];
	if(sum[cnt[x]]>0)sum[cnt[x]]--;
	sum[++cnt[x]]++;
	res = max(res, cnt[x]);
}
void erase(int pos)
{
	x = v[pos];
	if (sum[cnt[x]] > 0)sum[cnt[x]]--;
	if (res == cnt[x])
	{
		if (sum[cnt[x]] == 0)
		{
			res--;
		}
	}
	if (cnt[x] > 0)
	{
		sum[--cnt[x]]++;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	memset(sum, 0, sizeof(sum));
	memset(cnt, 0, sizeof(cnt));
	cin >> n >> m;
	len = sqrt(n);
	for (int i = 1; i <= n; ++i)
	{
		cin >> v[i];
		lsh_v[i] = v[i];
	}
	sort(lsh_v + 1, lsh_v + 1 + n);
	lsh_len = unique(lsh_v + 1, lsh_v + 1 + n) - lsh_v - 1;
	for (int i = 1; i <= n; ++i)
	{
		v[i] = lower_bound(lsh_v + 1, lsh_v + 1 + lsh_len,v[i]) - lsh_v;
	}
	for (int i = 1; i <= m; ++i)
	{
		cin >> l >> r;
		q[i] = query(l,r,i);
	}
	sort(q+1,q+m+1);
	for (int i = 1; i <= m; ++i)
	{
		while (nowr < q[i].R)add(++nowr);
		while (nowl > q[i].L)add(--nowl);
		while (nowr > q[i].R)erase(nowr--);
		while (nowl < q[i].L)erase(nowl++);
		ans[q[i].ID] = res;
	}
	for (int i = 1; i <= m; ++i)
	{
		cout << ans[i] << endl;
	}
	//system("pause");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注