3038 「JOISC 2019 Day3」穿越时空 Bitaro

题目译自 JOISC 2019 Day3 T3「時をかけるビ太郎 / Bitaro, who Leaps through Time」

在河狸国，一条路上有 $N$ 座城市，依次编为 $1\ldots N$ 号；连接城市 $i$ 和城市 $i+1$ 的那段路被称为 $i$ 号路。在河狸国，一天有 $10^9$ 秒，依次称为时刻 $0\ldots 10^9-1$。从城市 $i$ 沿路到达与之相邻的城市——城市 $i-1$ 或城市 $i+1$ 需要 $1$ 个单位时间。$i$ 号路每天在时刻 $L_i$ 到时刻 $R_i$ 之间开放通行。具体说来，为了通过 $i$ 号道路，我们必须在满足 $L_i\le x\le R_i-1$ 的时刻 $x$ 从城市 $i$ 或城市 $i+1$ 出发，在 $x+1$ 时刻到达另一城市。

Bitaro 原本是一位住在河狸国的普通河狸，然而，为了改掉自己迟到的坏习惯，他最终获得了穿越时空的技能。每次使用这个技能，他能回到一秒前。但他不能回到前一天：也就是说，如果他在 $0$ 时刻与 $1$ 时刻之间使用技能，他只能回到这一天的 $0$ 时刻。他只能在城市里使用这个技能。使用这个技能不会改变他的位置。

穿越时空会让 Birato 变累。为了找到能从一个城市到另一个城市且使用技能次数最少的方法，他决定进行一个 $Q$ 步的想象试验。第 $j$ 步实验是以下两种情况之一： - 改变 $P_j$ 号道路的开放时间，改后 $P_j$ 号道路在时刻 $S_j$ 到时刻 $E_j$ 开放通行； - 假设时刻 $B_j$ 他在城市 $A_j$，然后计算在这一天的时刻 $D_j$ 他要到达城市 $C_j$ 的话至少需要使用多少次技能。

他很想知道实验结果。

从标准输入中读入以下数据：

第一行两个正整数 $N,Q$，意义如题目描述。

接下来 $N-1$ 行，每行两个非负整数 $L_i,R_i$，意义如题目描述。

接下来 $Q$ 行，每行四到五个整数，设 $T_j$ 为这 $Q$ 行中每行的第一个数： - $T_j=1$ 时，这一行有四个整数 $T_j,P_j,S_j,E_j$，意味着第 $j$ 步实验将 $P_j$ 号道路的开放时间改为从 $S_j$ 到 $E_j$； - $T_j=2$ 时，这一行有五个整数 $T_j,A_j,B_j,C_j,D_j$，意味着第 $j$ 步实验查询假设在时刻 $B_j$ 时 Bitaro 在城市 $A_j$，他要在时刻 $D_j$ 到达城市 $C_j$ 最少的使用技能次数。

对于每个 $T_j=2$ 的询问，向标准输出输出一个整数，表示答案。

第一步试验，Bitaro 用 $1$ 秒从城市 $1$ 到城市 $2$，然后再用 $1$ 秒从城市 $2$ 到城市 $3$。到达城市 $3$ 时是时刻 $5$，于是用两次技能回到时刻 $3$。

第二步试验，将第 $2$ 条道路，也就是城市 $2$ 到城市 $3$ 的道路开放时间改为时刻 $0$ 到时刻 $1$ 之间开放。

第三步试验，Bitaro 用 $1$ 秒从城市 $1$ 到了城市 $2$，此时为时刻 $4$，然后用四次技能回到时刻 $0$，再从城市 $2$ 到城市 $3$，并在城市 $3$ 处等了两秒。

对于全部数据： - $1\le N,Q\le 3\times 10^5$； - $0\le L_i\lt R_i\le 10^9-1\ (1\le i\le N-1)$； - 当 $T_j=1$ 时，$1\le P_j\le N-1,0\le S_j\lt E_j\le 10^9-1\ (1\le j\le Q)$； - 当 $T_j=2$ 时，$1\le A_j,C_j\le N,0\le B_j,D_j\le 10^9-1\ (1\le j\le Q)$。

子任务及附加条件如下： - 子任务 $1$（$4$ 分）：$N,Q\le 10^3$； - 子任务 $2$（$30$ 分）：对于实验中所有步骤，$T_j=2$； - 子任务 $3$（$66$ 分）：无附加限制。