7451: [AHOI2021初中组] 地铁
[Creator : ]
Description
[AHOI2021初中组] 地铁
题目背景
AHOI2021 初中组 T4
**你可以选择跳过背景部分。**
小可可发现自己所学算法在生活中其实无大用，感觉十分沮丧。小雪见状还是嘀咕了几句“应该还是有用的吧”。
“不过没用又怎么样呢？算法只不过是一块名牌大学的敲门砖罢了。”
“你这话我就不同意了。跳蚤国王曾经和我说过，以后科研或者工作中我们还会和信息学竞赛中的某些东西重逢，虽然可能不会再有信息学竞赛这么难。
“除开功利的因素之外，搞信息学竞赛还是能享受到很多思考的乐趣的。”
“你说的也对。每次我在考场上不会做质疑这题是不是有问题的时候，考后看题解总是懊恼又快乐——这么自然的思路我怎么想不到呢！”
一颗理论计算机科学家的种子悄悄萌芽。
沙尘暴突然神奇般的散去了。实在坐不下去的两人决定出门坐地铁瞎逛，随性下车。即使没有刻意为之，小雪在地铁上却想出了一个有意思的问题，你能解决吗？
题目描述
B 市的地铁历史悠久，小雪和小可可乘坐的 X 号线是环形路线，上面分布着 $n$ 个车站，**相邻两个车站之间的铁路长度为正整数**。现在小雪进行了一些观察，得到了 $m$ 条信息，第 $i$ 条信息是如下形式之一：
1. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不小于一个给定的值 $L_i$（$S_i$ 和 $T_i$ 是两个车站）；
2. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不大于一个给定的值 $L_i$。
小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。
题目背景
AHOI2021 初中组 T4
**你可以选择跳过背景部分。**
小可可发现自己所学算法在生活中其实无大用，感觉十分沮丧。小雪见状还是嘀咕了几句“应该还是有用的吧”。
“不过没用又怎么样呢？算法只不过是一块名牌大学的敲门砖罢了。”
“你这话我就不同意了。跳蚤国王曾经和我说过，以后科研或者工作中我们还会和信息学竞赛中的某些东西重逢，虽然可能不会再有信息学竞赛这么难。
“除开功利的因素之外，搞信息学竞赛还是能享受到很多思考的乐趣的。”
“你说的也对。每次我在考场上不会做质疑这题是不是有问题的时候，考后看题解总是懊恼又快乐——这么自然的思路我怎么想不到呢！”
一颗理论计算机科学家的种子悄悄萌芽。
沙尘暴突然神奇般的散去了。实在坐不下去的两人决定出门坐地铁瞎逛，随性下车。即使没有刻意为之，小雪在地铁上却想出了一个有意思的问题，你能解决吗？
题目描述
B 市的地铁历史悠久，小雪和小可可乘坐的 X 号线是环形路线，上面分布着 $n$ 个车站，**相邻两个车站之间的铁路长度为正整数**。现在小雪进行了一些观察，得到了 $m$ 条信息，第 $i$ 条信息是如下形式之一：
1. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不小于一个给定的值 $L_i$（$S_i$ 和 $T_i$ 是两个车站）；
2. 环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不大于一个给定的值 $L_i$。
小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。
Input
第一行两个空格隔开的正整数 $n$ 和 $m$。
下面 $m$ 行，第 $i$ 行四个空格隔开的正整数 $type_i,S_i,T_i,L_i$，其中 $type_i \in \{1,2\}$ 表示信息的类型。车站顺时针编号为从 1 开始的连续整数。保证 $1 \le S_i,T_i \le n$ 且 $S_i \ne T_i$。
下面 $m$ 行，第 $i$ 行四个空格隔开的正整数 $type_i,S_i,T_i,L_i$，其中 $type_i \in \{1,2\}$ 表示信息的类型。车站顺时针编号为从 1 开始的连续整数。保证 $1 \le S_i,T_i \le n$ 且 $S_i \ne T_i$。
Output
仅一行一个整数，表示所求答案。如果有无穷种取值，请输出 `-1`。
保证答案不为 0，即至少有一种可能的方案。
保证答案不为 0，即至少有一种可能的方案。
Constraints
对于 $30\%$ 的数据，保证 $n,m \le 9$，$L_i \le 5$；
对于另外 $15\%$ 的数据，保证 $T_i$ 是 $S_i$ 顺时针方向后第一个车站；
对于另外 $20\%$ 的数据，保证 $T_i$ 是 $S_i$ 顺时针方向后第二个车站；
对于另外 $25\%$ 的数据，保证 $n,m \le 50$；
对于 $100\%$ 的数据，保证 $3 \le n \le 500$，$1 \le m \le 500$，$1 \le L_i \le 10^9$。
对于另外 $15\%$ 的数据，保证 $T_i$ 是 $S_i$ 顺时针方向后第一个车站；
对于另外 $20\%$ 的数据，保证 $T_i$ 是 $S_i$ 顺时针方向后第二个车站；
对于另外 $25\%$ 的数据，保证 $n,m \le 50$；
对于 $100\%$ 的数据，保证 $3 \le n \le 500$，$1 \le m \le 500$，$1 \le L_i \le 10^9$。
Sample 1 Input
4 6
1 1 3 3
2 2 4 5
1 2 4 4
1 3 1 4
2 4 2 5
1 4 2 3
Sample 1 Output
4
定义数组 $d[1..4]$，其中 $d[i]$ 表示 $i$ 号车站顺时针到 $i+1$ 号车站的铁路长度。
1. $d=[1,2,2,2]$，总长度为 $7$；
2. $d=[1,2,2,3]$，总长度为 $8$；
3. $d=[1,2,2,4]$，总长度为 $9$；
4. $d=[1,2,3,4]$，总长度为 $10$。
可以证明，不存在其他的可能长度，于是答案为 $4$。
1. $d=[1,2,2,2]$，总长度为 $7$；
2. $d=[1,2,2,3]$，总长度为 $8$；
3. $d=[1,2,2,4]$，总长度为 $9$；
4. $d=[1,2,3,4]$，总长度为 $10$。
可以证明，不存在其他的可能长度，于是答案为 $4$。
Sample 2 Input
3 2
2 1 2 1
2 2 3 1
Sample 2 Output
-1
$3$ 号车站顺时针到 $1$ 号车站的铁路长度可以为任意正整数。