U494458 『F.w.b』追梦人

> 最初のステップ\ > 再び涙\ > 彫刻された風景\ > 黄昏に消えていく風\ > 夢の終わりまで

有一排 $n$ 间房屋（$1,2,3,...,n-1,n$），每间房屋都有一个窗户，每个人都能从窗户中看到自己喜欢的人，所以他们总是会在房屋之间来回穿梭。 当编号为 $i$ 的人看到了自己喜欢的人 $j$ 时，编号为 $i$ 的人不能立刻赶出去，因为那样太明显了。他会等编号为 $j$ 的人走远之后，才向着他走去的方向追去。由于这是一个一维问题，所以只需要考虑向负方向（$-$）或正方向（$+$）就可以了。 当 $i$ 追出去以后，他只能判断 $j$ 的方向，但是无法确定 $j$ 在哪一栋楼房。但是由于 $i$ 十分有钱（这里确保每一个人都十分有钱，包括 $j$，因为 $j$ 也可能喜欢别人），所以 $i$ 会将他觉得 $j$ 可能去往的房子都买下来，同时将他原有的**所有**房子都卖掉。保证他觉得 $j$ 所去往的房子是一个连续的区间 $[x,y]$ 而且 $j$ 一定在区间 $[x,y] 中$。当然，如果 $a$ 房子本来就有居民（$a\in[x,y]$），那么 $i$ 不会买下来。 现在想知道，在许多村民的几经波折后，$[l,r]$ 区间中，还有哪些房子是被人买**着**的。

第一行输入两个正整数 $n,q$，表示一维问题的 $n$ 间房屋和 $q$ 次询问（一开始 $n$ 间房屋中都没有人）。 接下来 $q$ 行，每行为以下两种操作之一： - $op=1,id,x,y$ 表示编号为 $id$ 的人，卖掉了之前的所有房子，买下了 $[x,y]$ 的房子。 - $op=2,l,r$ 询问 $[l,r]$ 中有多少房子被人买**着**。 **不保证 $id$ 顺序递增且相差为 $1$**。

输出每一个 $op=2$ 的询问的答案。

### 样例解释 #1 第一个人住进了 $[2,3]$，$[0,1,1,0,0]$。 第二个人住进了 $[4,5]$，$[0,1,1,2,2]$。 第一个人搬进了 $[3,5]$，$[0,0,1,2,2]$（因为 $4,5$ 被 $2$ 买了，所以实际上 $1$ 只搬进了 $3$ 号房屋）。 故输出 $3$。 ### 数据范围 对于 $20\%$ 的数据，$q\le10$。 对于 $50\%$ 的数据，$n,q\le1000$。 对于 $100\%$ 的数据，$n\le10^5$，$q\le10^3$，$id$ 在 $int$ 范围内，保证每一组输入数据均合法。 **数据保证随即构造。** **请注意本题的时间与空间限制。题目的空间和时间限制均可以通过正解。且保证 50 pts 暴力可以通过 50% 的数据。**