#3038. 「JOISC 2019 Day3」穿越时空 Bitaro

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hiuseues2

题目描述

题目译自 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 的询问,向标准输出输出一个整数,表示答案。

样例

样例输入 1

3 3
0 5
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3

样例输出 1

2
4

样例说明 1

第一步试验,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

5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5

样例输出 2

4
3
2
3

样例输入 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

样例输出 3

145611455
0
447180143
0
207252171
0
0

样例输入 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

样例输出 4

10467449
164858601

数据范围与提示

对于全部数据:

  • 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 分):无附加限制。