此题为标记的加强版
此题和标记有很大不同,请注意.
滥用此题卡评测将被制裁.
题目描述
玩过原神的人基本都知道,纳西妲的元素战技『所闻遍计』会标记敌人.现在给定你敌人的数量,假设每一次操作会使a敌人被标记(可以重复标记),纳西妲会问你[l,r]区间内没有被标记过的敌人数量.
注意:标记不会消失.
标记操作格式为:1 a.
询问格式为2 l r,不保证l<=r.
敌人标号从1开始.
格式
输入
第一行:n,q,表示敌人个数和总操作及询问次数.
之后q行:操作以及询问.
输出
查询结果.
样例
5 6
1 3
1 5
2 1 4
2 2 5
1 2
2 1 3
3
2
1
数据范围
| 测试点编号 |
数据范围 |
| 1(2s) |
1≤q≤102,1≤n,l,r,a≤2×102 |
| 2(2s) |
1≤q≤105,1≤n,l,r,a≤5×105 |
| 3−9(2s) |
1≤q≤106,1≤n,l,r,a≤5×105 |
| 10(4s) |
1≤q≤2×106,1≤n,l,r,a≤1×106 |
