欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[BZOJ 4241] 历史研究

程序员文章站 2022-05-27 18:56:43
...

BZOJ传送门

题目描述

IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。

日记中记录了连续NN天发生的时间,大约每天发生一件。

事件有种类之分。第ii(1iN)(1\le i\le N)发生的事件的种类用一个整数XiX_i表示,XiX_i越大,事件的规模就越大。

JOI教授决定用如下的方法分析这些日记:

  1. 选择日记中连续的一些天作为分析的时间段

  2. 事件种类tt的重要度为tt*(这段时间内重要度为tt的事件数)

  3. 计算出所有事件种类的重要度,输出其中的最大值

现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

输入输出格式

输入格式

第一行两个空格分隔的整数NNQQ,表示日记一共记录了NN天,询问有QQ次。

接下来一行NN个空格分隔的整数X1...XNX_1...X_NXiX_i表示第ii天发生的事件的种类

接下来QQ行,第ii(1iQ)(1\le i\le Q)有两个空格分隔整数AiA_iBiB_i,表示第ii次询问的区间为[Ai,Bi][A_i,B_i]

输出格式

输出QQ行,第ii(1iQ)(1\le i\le Q)一个整数,表示第ii次询问的最大重要度

输入输出样例

输入样例#1:

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

输出样例#1:

9
8
8
16
16

解题分析

如果用普通莫队在删除时无法维护次大值, 需要一个setset, 就GG了。

所以去学了新姿势: 回滚莫队。

还是分块, 把左端点在一块的询问按右端点从小到大排序。

如果左右端点都在一块先处理掉。

然后我们只维护左端点在当前左端点所在块最右端, 且右端点单调递增的答案, 每次动态插入左边块内的元素统计答案后再撤销。

总复杂度还是QNQ\sqrt N的。

代码如下:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <vector>
#include <tr1/unordered_map>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 100500
#define ll long long
template <class T>
IN void in(T &x)
{
	x = 0; R char c = gc;
	for (; !isdigit(c); c = gc);
	for (;  isdigit(c); c = gc)
	x = (x << 1) + (x << 3) + c - 48;
}
template <class T> IN T max(T a, T b) {return a > b ? a : b;}
std::tr1::unordered_map <int, int> mp;
int n, m, sqr, qcnt, arr, bcnt;
ll ans[MX];
int blk[MX], val[MX], cnt[MX], id[MX];
struct Query {int l, r, id;};
IN bool operator < (const Query &x, const Query &y) {return x.r < y.r;}
std::vector <Query> que[500];
int main(void)
{
	int foo, bar, cur, siz;
	R ll rem, mx;
	in(n), in(m); sqr = std::sqrt(n); bcnt = n / sqr;
	for (R int i = 1; i <= n; ++i)
	{
		in(foo), blk[i] = i / sqr;
		if (!mp[foo]) mp[foo] = ++arr, val[arr] = foo;
		id[i] = mp[foo];
	}
	for (R int i = 1; i <= m; ++i)
	{
		in(foo), in(bar);
		if (blk[foo] == blk[bar])
		{
			mx = 0;
			for (R int j = foo; j <= bar; ++j)
			{
				++cnt[id[j]];
				mx = max(1ll * cnt[id[j]] * val[id[j]], mx);
			}
			ans[i] = mx; mx = 0;
			for (R int j = foo; j <= bar; ++j) --cnt[id[j]];
		}
		else que[foo / sqr].push_back({foo, bar, i});
	}
	std::sort(que + 1, que + 1 + qcnt);
	for (R int i = 0; i <= bcnt; ++i)
	{
		std::sort(que[i].begin(), que[i].end());
		std::memset(cnt, mx = 0, sizeof(cnt));
		cur = (i + 1) * sqr - 1, siz = que[i].size();
		for (R int j = 0; j < siz; ++j)
		{
			W (cur < que[i][j].r)
			{
				++cur;
				++cnt[id[cur]];
				mx = max(mx, 1ll * cnt[id[cur]] * val[id[cur]]);
			}
			rem = mx;
			for (R int k = (i + 1) * sqr - 1; k >= que[i][j].l; --k)
			{
				++cnt[id[k]];
				mx = max(mx, 1ll * cnt[id[k]] * val[id[k]]);
			}
			ans[que[i][j].id] = mx;
			for (R int k = (i + 1) * sqr - 1; k >= que[i][j].l; --k) --cnt[id[k]];
			mx = rem;
		}
	}
	for (R int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
相关标签: 莫队