← 返回题目列表

Codeforces · 2026/F

F. Bermart 冰淇淋

中文机器翻译题面 查看原题

在Bermart连锁店里,出售各种冰淇淋。每种冰淇淋都有两个参数:价格和口味。

最初,有一家编号为 $$$1$$$ 的商店,什么也不卖。您必须处理以下类型的 $$$q$$$ 查询:

- $$$1~x$$$ — 一家新店开业,销售与商店 $$$x$$$ 相同类型的冰淇淋。它接收最小可用正索引。新店的冰淇淋种类顺序与店内$$$x$$$相同。
- $$$2~x~p~t$$$ — 一种价格为 $$$p$$$、味道为 $$$t$$$ 的冰淇淋在商店 $$$x$$$ 上架。
- $$$3~x$$$ — 商店中存货时间最长(最早出现)的一种冰淇淋 $$$x$$$ 被移除。
- $$$4~x~p$$$ — 对于商店$$$x$$$,找到那里出售的冰淇淋类型子集的最大总口味,使得总价不超过$$$p$$$(每种类型只能在该子集中使用一次)。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^4$$$) — 查询数。

以下 $$$q$$$ 行中的每一行均包含语句中描述的格式的查询:

- $$$1~x$$$;
- $$$2~x~p~t$$$ ($$$1 \le p, t \le 2000$$$);
- $$$3~x$$$;
- $$$4~x~p$$$ ($$$1 \le p \le 2000$$$)。

输入数据的附加约束:

- 每次查询中的$$$x$$$不超过当前商店数量(即$$$1$$$加上$$$1$$$类型查询的数量);
- 查询类型 $$$3$$$ 不适用于没有冰淇淋类型的商店;
- 至少有一个 $$$4$$$ 类型的查询。

输出

对于 $$$4$$$ 类型的每个查询,输出一个整数 - 对于商店 $$$x$$$,找到在那里出售的冰淇淋类型子集的最大总美味,使得总价格不超过 $$$p$$$(每种类型只能在子集中使用一次)。

示例

输入 #1

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

输出 #1

4
11
0
11
17
4
17