数据结构刷题记录

AT1219 歴史の研究 - 莫队

• 简单的回滚莫队，考虑到维护最大值，加操作好做而减操作难
• 还可以将每个数可能的贡献算出，即对于一个数x，贡献为x1,x2,...,x*y(y为在整个序列中x出现个数），离散化后，用值域分块维护，只用普通莫队即可
• 下面是回滚莫队做法的代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, m, len;
long long a[MAXN], b[MAXN], dr[MAXN];
int block, bn, B[MAXN];
long long ans, cm[MAXN], Ans[MAXN], ct[MAXN];
int s[MAXN], st;
struct question
{
	int l, r, id;
}ask[MAXN];
inline bool cmp(const question &a, const question &b)
{
	if(B[a.l] ^ B[b.l]) return B[a.l] < B[b.l];
	return a.r < b.r;
}
inline long long max(const long long &x, const long long &y)
{
	return x > y ? x : y;
}
inline long long min(const long long &x, const long long &y)
{
	return x < y ? x : y;
}
inline void discrete()
{
	len = 0;
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++)
	{
		if(i == 1 || b[i] != b[i - 1]) 
			dr[++len] = b[i]; 
	}
}
inline long long calc(int l, int r)
{
	long long res = 0;
	for (int i = l; i <= r; i++) cm[a[i]] = 0;
	for (int i = l; i <= r; i++)
	{
		cm[a[i]]++;
		res = max(cm[a[i]] * dr[a[i]], res);
	}
	return res;
}
int main()
{
	scanf("%d %d", &n, &m); block = pow(n, 1.0 / 2.0);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
	discrete();
	for (int i = 1; i <= n; i++) a[i] = lower_bound(dr + 1, dr + len + 1, a[i]) - dr;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &ask[i].l, &ask[i].r);
		ask[i].id = i;
	}
	for (int i = 1; i <= n; i++) B[i] = (i - 1) / block + 1;
	sort(ask + 1, ask + m + 1, cmp);
	bn = B[n];
	for (int i = 1, j = 1; i <= bn; i++)
	{
		int br = min(n, i * block), l = br + 1, r = br;
		st = 0;//s数组维护出现了那些数
		ans = 0;
		for (; B[ask[j].l] == i; j++)
		{
			if(B[ask[j].r] == i)
			{
				Ans[ask[j].id] = calc(ask[j].l, ask[j].r);
				continue;
			}
			while(r < ask[j].r)
			{
				r++;
				if(!ct[a[r]]) s[++st] = a[r];
				ct[a[r]]++; ans = max(ans, ct[a[r]] * dr[a[r]]);
			}
			long long tmp = ans;
			while(l > ask[j].l)
			{
				l--;
				ct[a[l]]++; tmp = max(tmp, ct[a[l]] * dr[a[l]]);
			}
			Ans[ask[j].id] = tmp;
			while(l <= br)
			{
				ct[a[l]]--;
				l++;
			}
		}
		for (int i = 1; i <= st; i++) ct[s[i]] = 0;
	}
	for (int i = 1; i <= m; i++) printf("%lld\n", Ans[i]);
	return 0;
}

数据结构刷题

原文：https://www.cnblogs.com/hangzz/p/13258840.html