#6515. 「雅礼集训 2018 Day10」贪玩蓝月

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

大渣好,我四渣渣辉,点一下,玩一年,装备不花一分钱,说话战斗,罩杯回收,找一基友,极限到手。

0 元 VIP,3 天满级,一秒一刀 999,装备全爆 666,广告做得再牛,不如进服遛一遛!

古天乐绿了,古天乐绿了,惊喜不断,月入上万!不花钱还赚钱的绿色游戏,等级能提现,装备换点钱!

《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备,每件装备有一个特征值 w 和一个战斗力 v 。在每种特定的情况下,你都要选出特征值的和对 p 取模后在一段范围内的装备,而角色死亡时自己的装备会爆掉。每个角色的物品槽可以看成一个双端队列,得到的装备会被放在两端,自己的装备爆掉也会在两端被爆。

现在我们有若干种事件和询问,如下所示:

  • IF w v:在前端加入一件特征值为 w 战斗力为 v 的装备
  • IG w v:在后端加入一件特征值为 w 战斗力为 v 的装备
  • DF:删除最前端的装备
  • DG:删除最后端的装备
  • QU l r:在当前的装备中选取若干装备,他们的和对 p 取模后在 [l, r] 中,使得这些装备的战斗力之和最大

为了锻炼你的水平,请尽量使用在线做法。

输入格式

第一行一个整数表示测试点编号。

第二行两个整数 m p ,分别表示操作数和模数。

接下来每一行一个操作,如题目描述中所述,有五种操作,在前后加或删一件物品或者询问。

输出格式

对于每个询问,输出一行,表示在当前装备中选取若干装备和对 p 取模后在 [l, r] 的装备,使得这些装备战斗力之和最大。如果没有合法方案,输出 -1

样例

样例输入 1

0
11 10
QU 0 0
QU 1 9
IG 14 7
IF 3 5
QU 0 9
IG 1 8
DF
QU 0 4
IF 1 2
DG
QU 2 9

样例输出 1

0
-1
12
8
9

样例解释 1

一开始没有物品,那么可以不选,特征值价值为 0 ,不可能凑出非 0 的特征值。

然后在后面加了一个特征值 14 价值 7 的装备,又在前面加了一个特征值 3 价值 5 的装备,询问特征值取模后为 [0, 9] 的装备,那么全部选择价值为 12

然后在后面加了一个特征值为 1 价值为 8 的装备,删除了最前面的装备(特征值 3 价值 5 ),询问特征值取模后为 [0, 4] 的装备,那么只选择特征值为 1 价值为 8 的装备,最大价值为 8

最后又在前面加了一个特征值为 1 价值为 2 的装备,删除了最后面的装备(特征值 1 价值 8 ),询问特征值取模后为 [2, 9] 的装备,那么选择当前剩余的两件装备,价值和为 9

数据范围与提示

测试点编号 m p 特殊情况
1 \leq 10
2 \leq 20
3 \leq 100
4 \leq 200
5 \leq 3000 \leq 10
6 保证询问中有 l = r
7
8 = 2
9 \leq 3
10 \leq 5
11 \leq 10
12 只有 IFIG 操作和询问
13 只有 IGDG 操作和询问
14
15 只有 IGDG 操作和询问,且保证询问中有 l = r
16 保证询问中有 l = r
17 只有 IGDF 操作和询问
18
19 \leq 25000
20

对于所有数据, m \leq 50000, p \leq 500, 0 \leq w, v < 10^9 ,保证没有物品时不会进行删除操作。