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

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

题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

对于每个询问,输出一行,表示在当前装备中选取若干装备和对 pp 取模后在 [l,r][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
0
-1
12
8
9

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

然后在后面加了一个特征值 1414 价值 77 的装备,又在前面加了一个特征值 33 价值 55 的装备,询问特征值取模后为 [0,9][0, 9] 的装备,那么全部选择价值为 1212

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

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

数据范围与提示

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

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