Dotcpp  >  编程题库  >  蓝桥杯2019年第十届国赛真题-第八大奇迹
题目 2565:

蓝桥杯2019年第十届国赛真题-第八大奇迹

时间限制: 2s 内存限制: 192MB 提交: 291 解决: 33

题目描述

在一条 R 河流域,繁衍着一个古老的名族 Z。他们世代沿河而居,也在河边发展出了璀璨的文明。
Z 族在 R 河沿岸修建了很多建筑,最近,他们热衷攀比起来。他们总是在比谁的建筑建得最奇特。
幸好 Z 族人对奇特的理解都差不多,他们很快给每栋建筑都打了分,这样评选谁最奇特就轻而易举了。
于是,根据分值,大家很快评出了最奇特的建筑,称为大奇迹。后来他们又陆续评选了第二奇特、第二奇特、……、第七奇特的建筑,依次称为第二大奇迹、第三大奇迹、……、第七大奇迹。
最近,他们开始评选第八奇特的建筑,准备命名为第八大奇迹。在评选中,他们遇到了一些问题。
首先,Z 族一直在发展,有的建筑被拆除又建了新的建筑,新建筑的奇特值和原建筑不一样,这使得评选不那么容易了。
其次,Z 族的每个人所生活的范围可能不一样,他们见过的建筑并不是所有的建筑,他们坚持他们自己所看到的第八奇特的建筑就是第八大奇迹。
Z 族首领最近很头疼这个问题,他害怕因为意见不一致导致 Z 族发生分歧。他找到你,他想先了解一下,民众自己认为的奇迹是怎样的。
现在告诉在 R 河周边的建筑的变化情况,以及在变化过程中一些人的生活范围,请编程求出每个人认为的第八大奇迹的奇特值是多少。

输入格式

输入的第一行包含两个整数 L, N,分别表示河流的长度和要你处理的信息的数量。开始时河流沿岸没有建筑,或者说所有的奇特值为 0。接下来 N 行,每行一条你要处理的信息。

如果信息为 C p x,表示流域中第 p 个位置 (1 ≤ p ≤ L) 建立了一个建筑,其奇特值为 x。如果这个位置原来有建筑,原来的建筑会被拆除。如果信息为 Q a b,表示有个人生活的范围是河流的第 a 到 b 个位置(包含 a 和 b,a ≤ b),这时你要算出这个区间的第八大奇迹的奇特值,并输出。如果找不到第八大奇迹,输出 0。

输出格式

对于每个为 Q 的信息,你需要输出一个整数,表示区间中第八大奇迹的奇特值。

样例输入

10 15
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10

样例输出

0
30
10
20

提示

对于 20% 的评测用例,1 ≤ L ≤ 1000, 1 ≤ N ≤ 1000。
对于 40% 的评测用例,1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000。
对于 100% 的评测用例,1 ≤ L ≤ 100000,1 ≤ N ≤ 100000。所有奇特值为
不超过 109 的非负整数。

标签