穿越时空 Bitaro

题号：NC53277
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

题目译自 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行，每行两个非负整数，意义如题目描述。
接下来Q行，每行四到五个整数，设为这Q行中每行的第一个数：
时，这一行有四个整数，意味着第j步实验将号道路的开放时间改为从到；时，这一行有五个整数，意味着第j步实验查询假设在时刻时Bitaro在城市，他要在时刻到达城市最少的使用技能次数。

输出描述:

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

示例1

输入

复制

输出

复制

2
4

说明

第一步试验，Bitaro用1秒从城市1到城市2，然后再用1秒从城市2到城市3。到达城市3时是时刻5，于是用两次技能回到时刻3。
第二步试验，将第2条道路，也就是城市2到城市3的道路开放时间改为时刻0到时刻1之间开放。
第三步试验，Bitaro用1秒从城市1到了城市2，此时为时刻4，然后用四次技能回到时刻0，再从城市2到城市3，并在城市3处等了两秒。

示例2

输入

复制

输出

复制

示例3

输入

复制

7 7
112103440 659752416
86280800 902409187
104535475 965602300
198700180 945132880
137957976 501365807
257419446 565237610
2 4 646977260 7 915994878
2 1 221570340 6 606208433
2 7 948545948 4 604273995
2 7 247791098 5 944822313
2 7 250362511 2 50167280
2 3 364109400 4 555412865
2 7 33882587 7 186961394

输出

复制

示例4

输入

复制

7 7
535825574 705426142
964175291 996597835
481817391 649559926
4519006 410772613
74521477 274584126
256535565 899389890
1 6 511428966 602601933
1 1 69986642 201421232
2 3 636443425 4 625975977
1 6 235225515 405336399
2 3 866680458 3 701821857
1 6 180606048 900533151
1 6 612564160 720179605

输出

复制

10467449
164858601

备注:

对于全部数据：
；
；
当时，；
当时，。

CC-BY-SA，感谢LOJ分享，译文来自  https://loj.ac/problem/3038