#P4811. [COCI2014-2015#3] KAMIONI

[COCI2014-2015#3] KAMIONI

题目描述

译自 COCI 2014/2015 Contest 3 T6「KAMIONI」

有一条马路,我们将其视为一条数轴。马路上有 NN 辆卡车,开始时,卡车都在整点上。所有卡车一起开始移动,并且都以同样的速率移动。没有卡车保持静止。每辆卡车花 11 分钟可以移动 11 个单位距离。

给出每辆卡车的「路线」。路线用一个含有 kk 个元素的数组 A1,A2,,AkA_1,A_2,\dots,A_k 表示。该卡车首先 A1A_1 开往 A2A_2,然后立即掉头开往 A3A_3,以此类推。忽略掉头的耗时。考虑到卡车会掉头,我们保证:

$$A_1 < A_2 > A_3 < A_4 > \dots\ \mathrm{or}\ A_1 > A_2 < A_3 > A_4 < \dots $$

一条可能的路线为 25172→5→1→7(给出的点要么是起点,要么是终点,要么就是掉头的位置)。开始时卡车位于 22,出发 33 分钟后到达位置 55,接着掉头。卡车继续行驶到位置 11 ,此时距出发已过去了 77 分钟。卡车再次掉头,并行驶到位置 77,此时距出发已经经过了 1313 分钟。

当卡车到达路线终点后,会有神秘的 Planet6174 外星人出现并把它带回飞船。

给出这 NN 辆卡车的路线。现在有 MM 组询问,每组询问包含两辆卡车。对于每组询问,请回答这对卡车出现在同一位置的次数。位置不一定是整数,比如它们可以在位置 2.52.5 相遇。

请注意,保证每一对询问的(而不是随便一对)卡车:

  • 其中一个被 Planet6174 外星人带走的时候,它们不会在同一位置。
  • 它们不会在初始时刻或是其中一个转弯的时候在同一位置。

Planet6174:翻译这道题目的人已经被解决掉了(滑稽

输入格式

第一行,两个整数 NNM(1N105,1M105)M(1 \le N \le 10^5,1 \le M \le 10^5),表示卡车的数量和询问的卡车的对数。

以下 NN 行,其中第 ii 行表示第 ii 辆卡车的路线。
每行第一个整数 Ki(1Ki3105)K_i(1 \le K_i \le 3 \cdot 10^5) 表示路线的长度。紧接着是 KiK_i 个整数 Aj(1Aj109)A_j(1 \le A_j \le 10^9),表示卡车 ii 路线上的点。给出的点要么是起点,要么是终点,要么就是掉头的位置。
所有卡车移动的总路程之和不会超过 31053 \cdot 10 ^5

以下 MM 行,其中第 ii 行包含两个整数 (ai,bi)(a_i,b_i),表示第 ii 个询问的两辆卡车。

输出格式

输出 MM 行,第 ii 行包含我们询问的第 ii 对卡车相遇的次数。

3 3
3 1 3 1
2 2 1
3 3 1 3
1 2
2 3
3 1
1
0
2
2 1
4 1 6 3 6
7 3 4 2 6 5 6 1
1 2
3
3 4
3 1 4 2
4 3 4 2 4
3 4 1 3
1 2
2 3
3 1
1 3
2
1
2
2

提示

对于 50%50\% 的数据,保证 N102,Ki103,M103N \le 10^2,K_i \le 10^3,M \le 10^3