手套 - 代码源竞赛平台

题目描述

一个手套仓库最初为空。手套有 $n$ 种尺码，编号为 $1,2,\ldots,n$，每种尺码的手套又分为左手套和右手套。

一只左手套和一只右手套可以配成一双，当且仅当它们的尺码相同。每只手套只能用于配成一双手套。

现在需要依次处理 $q$ 次操作。用 $t=1$ 表示左手套，$t=2$ 表示右手套。每次操作属于以下三种类型之一：

• 1 x t a：向仓库中放入 $a$ 只尺码为 $x$、类型为 $t$ 的手套。
• 2 x t a：从仓库中取出 $a$ 只尺码为 $x$、类型为 $t$ 的手套。如果这类手套不足 $a$ 只，则将这类手套全部取出。
• 3：查询当前仓库中的手套最多可以配成多少双，统计所有尺码的配对总数。

第三类操作只进行查询，不会取出手套或改变库存。请依次回答所有第三类操作。

输入格式

第一行包含两个整数 $n,q$，分别表示尺码的种类数和操作次数。

接下来 $q$ 行，每行描述一次操作，格式为 1 x t a、2 x t a 或 3，含义如题目描述所示。

输出格式

对于每次第三类操作，输出一行一个整数，表示当前仓库中的手套最多可以配成的总双数。

样例

5 13
1 2 1 5
1 2 2 3
3
2 2 1 4
3
1 2 1 2
3
2 2 2 5
3
1 4 1 2
1 4 2 4
1 2 2 1
3

3
1
3
0
3

1 9
1 1 1 1000000000
1 1 1 1000000000
1 1 2 1000000000
1 1 2 1000000000
1 1 1 1000000000
1 1 2 1000000000
3
2 1 1 1000000000
3

3000000000
2000000000

样例解释

对于样例 $1$，五次查询的情况依次如下：

• 尺码为 $2$ 的左、右手套分别有 $5$ 只和 $3$ 只，可以配成 $3$ 双；其他尺码均无库存，因此答案为 $3$。
• 取出 $4$ 只尺码为 $2$ 的左手套后，该尺码的左、右手套分别有 $1$ 只和 $3$ 只，因此答案为 $1$。
• 再放入 $2$ 只尺码为 $2$ 的左手套后，该尺码的左、右手套各有 $3$ 只，因此答案为 $3$。
• 随后要求取出 $5$ 只尺码为 $2$ 的右手套，但库存只有 $3$ 只，因此将它们全部取出。此时仓库中没有右手套，答案为 $0$。
• 最后，尺码为 $2$ 的左、右手套分别有 $3$ 只和 $1$ 只，可以配成 $1$ 双；尺码为 $4$ 的左、右手套分别有 $2$ 只和 $4$ 只，可以配成 $2$ 双。因此答案为 $1+2=3$。

对于样例 $2$，前六次操作后，尺码为 $1$ 的左、右手套各有 $3\times 10^9$ 只，因此第一次查询的答案为 $3\times 10^9$。取出 $10^9$ 只左手套后，第二次查询的答案为 $2\times 10^9$。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$1$
$2$	$30$	$100$
$3$	$50$	$2\times 10^5$

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$；操作类型为 $1$、$2$ 或 $3$；第一类和第二类操作中，$1\le x\le n$，$t\in\{1,2\}$，$1\le a\le 10^9$。