logo AlgoBeat OnlineJudge
登录 注册

#215045. [北大集训 2025] 小丑大师的荣耀

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

在小丑牌中达成成就「完美主义者 ++」后,伟大的 Balatro 贤者 Clonoth 决定考一考你对卡牌游戏的理解。

Clonoth 提出了以下问题:给定一个包含 张卡牌的牌堆,每张卡牌的正反面各写有一个 中的正整数。你可以选择若干张卡牌,将其正反面翻转。对于 ,若存在一种翻转方式,使得翻转后 中每个整数 都出现在至少一张卡牌的正面,则称区间 可覆盖的。形式化地,设第 () 张卡牌的正反面上的正整数分别为 ,则 是可覆盖的当且仅当存在一个长度为 的 01 串 ,满足对于所有 ,存在 满足

由于牌堆在游戏中是动态变化的,Clonoth 设计了一个动态场景。具体地,初始时牌堆为空,即 ,接下来 Clonoth 将会进行 次操作,每次操作是以下三种类型之一:

  1. 插入卡牌:给定正整数 (),令 ,然后向牌堆中插入一张编号为 ,正面为 ,反面为 的卡牌;
  2. 移除卡牌:给定正整数 (),满足编号为 的卡牌当前仍在牌堆中,然后从牌堆中移除该卡牌;
  3. 询问:给定正整数 (, ),你需要求出有多少个区间 满足 , 是可覆盖的。

如果你能正确回答所有询问,Balatro 贤者 Clonoth 就会赠予你一个珍贵的护符——「小丑大师的荣耀」!

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 ,表示卡牌上的数字的范围和操作次数。

输入的第 () 行包含若干个正整数,表示第 次操作,其中第一个正整数 表示第 次操作的类型。

  • ,则该行包含三个正整数 ,表示插入一张正面为 ,反面为 的卡牌;
  • ,则该行包含两个正整数 ,表示移除编号为 的卡牌;
  • ,则该行包含五个正整数 ,表示一次询问。

输出格式

输出到标准输出。

对于每次询问,输出一行一个非负整数,表示满足要求的区间数量。

样例

样例输入 1

8 10
1 6 5
3 2 3 8 8
1 3 3
1 4 5
3 2 6 6 8
1 1 2
2 4
1 2 5
3 1 3 2 7
3 2 3 2 3

样例输出 1

0
2
8
3

样例输入 2

9 17
1 6 6
3 1 1 3 3
1 5 1
1 3 4
2 2
1 9 9
1 2 2
1 7 9
2 4
1 2 3
3 1 7 3 3
1 8 6
1 7 5
3 6 9 9 9
1 4 5
2 3
3 3 5 2 9

样例输出 2

0
2
4
16

数据范围与提示

【子任务】

对于所有测试数据,均有:

  • 对于每次操作,均有 ,且给定的参数均满足【题目描述】中的限制。
子任务编号 分值 特殊性质
1 30
2 10 A
3 BC
4 20 B
5 C
6 10

特殊性质 A:所有插入卡牌与移除卡牌的操作均在所有询问之前。

特殊性质 B:不存在移除卡牌的操作。

特殊性质 C:所有询问均满足