当前位置:首页 > 莫队 > 正文
LOJ2874历史研究[JOISC2014Day1]
107+

题目大意:n个数,m次询问,每次询问区间最优值——数字乘以数字出现次数。

题目描述

**题目译自 JOISC 2014 Day1 T3「[歴史の研究](https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d1.pdf)」**

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

日记中记录了连续 $N$ 天发生的事件,每天发生一件事件。 事件有种类之分。第 $i$ 天发生的事件的种类用一个整数 $X_i$ 表示,$X_i$ 越大,事件的规模就越大。

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

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

2. 事件种类 $t$ 的重要度为 $t$ 与这段时间内重要度为 $t$ 的事件数的乘积;

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

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

输入格式

第一行两个空格分隔的整数 $N$ 和 $Q$,表示日记一共记录了 $N$ 天,询问有 $Q$ 次。 接下来一行 $N$ 个空格分隔的整数 $X_1\dots X_N$,$X_i$ 表示第 $i$ 天发生的事件的种类。 接下来 $Q$ 行,第 $i$ 行有两个空格分隔整数 $A_i$ 和 $B_i$,表示第 $i$ 次询问的区间为 $[A_i,B_i]$。

输出格式

输出 $Q$ 行,第 $i$ 行一个整数,表示第 $i$ 次询问的最大重要度。

Input

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

Output

9
8
8
16
16

解题思路

新增一个数比较容易实现:累加出现次数,顺便乘以自己尝试获得更大值。

删除一个数则不好维护答案,因为最大值消失后,不知道次大值是多少,这时我们可以用回滚操作,回到之前记录的答案那里。

1、对于区间不超过根号大小的,可以直接暴力,这些区间总的时间复杂度不超过$m\sqrt{n}$。

2、对于其他区间,按照左端点分成根号份,每一份右端点递增。右端点每次都是增加操作,不涉及删除容易维护。左端点有时往左走增加,有时往右走删除,往右时很难维护答案。这些区间至少两块,我们可以另pi为第二块的开头,由于右端点y都是不递减的,我们可以记录[pi, y]的答案,下一次询问是,我们可以将左端点往右走到pi,更新次数可以实现,更新答案直接用记录的值覆盖即可,这样后面又只剩下增加操作了,因为左端点肯定是在pi左边的,右端点肯定在y及其右边,我们只需要先拓展右端点,记录新的值,再拓展左端点就可以了。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

LOJ2874历史研究[JOISC2014Day1]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!