GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

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

编程题提高+/省选-

知识点

背包动态规划线段树

题目描述

> 大渣好，我四渣渣辉，点一下，玩一年，装备不花一分钱，说话战斗，罩杯回收，找一基友，极限到手。 > > 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

说明/提示

| 测试点编号 | $m$ | $p$ | 特殊情况 | | :-: | :-: | :-: | :-: | | 1 | $\leq 10$ | | | | 2 | $\leq 20$ | | | | 3 | $\leq 100$ | | | | 4 | $\leq 200$ | | | | 5 | $\leq 3000$ | $\leq 10$ | | | 6 | $\leq 3000$ | | 保证询问中有 $l = r$ | | 7 | $\leq 3000$ | | | | 8 | | $ = 2$ | | | 9 | | $\leq 3$ | | | 10 | | $\leq 5$ | | | 11 | | $\leq 10$ | | | 12 | | | 只有 IF，IG 操作和询问 | | 13 | | | 只有 IG，DG 操作和询问 | | 14 | | | 只有 IG，DG 操作和询问 | | 15 | | | 只有 IG，DG 操作和询问，且保证询问中有 $l = r$ | | 16 | | | 保证询问中有 $l = r$ | | 17 | | | 只有 IG，DF 操作和询问 | | 18 | | | 只有 IG，DF 操作和询问 | | 19 | $\leq 25000$ | | | | 20 | | | | | 对于所有数据， $m \leq 50000, p \leq 500, 0 \leq w, v < 10^9$，保证没有物品时不会进行删除操作。

上一题去做题下一题