『STA - R4』冰红茶

有 $n$ 个 bot 排成一排，每天所有 bot 都会喝冰红茶。 要求动态维护一排 bot，有三种操作或询问： - `1 l r k`，表示 $[l,r]$ 内的 bot 会喝 $k$ 瓶原味冰红茶、$[l,r]$ 外的 bot 会喝 $k$ 瓶热带风味冰红茶。 - `2 l r k`，表示 BTC 站长愤怒地把 $[l,r]$ 中最后连续喝了至少 $k$ 瓶口味相同的冰红茶的 bot 击毁。 - `3`，查询有多少个存活的 bot。 注：在 2 操作中，击毁不会改变 bot 的编号。 ## Input 第一行两个正整数 $n,q$。 后 $q$ 行，每行描述一个操作或询问，形如以下三种中的一种： - `1 l r k`； - `2 l r k`； - `3`。 ## Output 若干行，每行回答一个询问 3。 [samples] ## Background  某编程网站 BTC 长期在它的 Beginner Contest 的最后一题放科技模板题，于是 APJifengc 愤怒地在它的评测机上洒了若干瓶冰红茶，导致一些评测单元的运行速度快了 $10^{12}$ 倍，暴力跑得和正解一样快。 因为 BTC 不能出科技模板题了，所以 BTC 的站长想要让你维护一下 APJifengc 每次洒冰红茶后可用的评测单元个数，以便于统筹评测资源与灾后重建。 **已加入 Hack 数据，位于 Subtask 5，不计分。** ## Note ### 样例 1 解释 只说明操作 1 和操作 2。 第一次操作，三号和四号 bot 喝了 8 瓶原味冰红茶，其他 bot 喝了 8 瓶热带风味冰红茶。 第二次操作，三号和四号 bot 连续喝了 8 瓶原味冰红茶，被击毁，现在场上还有 3 个存活 bot。 第三次操作，二号 bot 喝了 3 瓶原味冰红茶，其他 bot 喝了 3 瓶热带风味冰红茶。 第四次操作，一号和五号 bot 连续喝了 11 瓶热带风味冰红茶，被击毁，现在场上还有 1 个存活 bot。 第五次操作，二号 bot 喝了 3 瓶原味冰红茶。 第六次操作，二号 bot 连续喝了 6 瓶原味冰红茶，被击毁，现在场上没有存活的 bot。 ### 数据范围 **本题采用捆绑测试。** - Subtask 1 (5pts)：$n,q\le 10^3$。 - Subtask 2 (20pts)：所有操作 2 中 $k\le 20$。 - Subtask 3 (25pts)：保证数据随机生成。 - Subtask 4 (50pts)：无特殊限制。 其中 Subtask 3 的测试数据生成方式如下： 1. 对于每次或询问，从三种类型中等概率选择一个； 2. 若选取的操作不为 3，那么从 $\left[1, n\right]$ 中等概率生成两个数 $l, r$，若 $l > r$，则交换 $l, r$，并将 $l, r$ 作为操作的参数； 3. 若选取的操作不为 3，那么从 $\left[1, 10^6\right]$ 中等概率生成一个数 $k$ 作为操作的参数。 对于全部数据，保证 $1\le n,q\le 2\times 10^5$，$1\le k\le 10^{6}$。