#P3602. 十万人的地铁

    ID: 2809 传统题 2000ms 512MiB 尝试: 36 已通过: 13 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理一维差分构造与建模不变量分析计算几何扫描线数据结构链表栈逆向还原操作CF2800

十万人的地铁

十万人的地铁

题目描述

陆仁甲和陆仁乙去搭地铁。陆仁甲要从循礼门去广埠屯,陆仁乙要从广埠屯去循礼门。两人都很清楚武汉地铁的收费规则。

武汉地铁 2 号线是一条直线,共有 mm 个地铁站,依次编号为 1,…,m1,\ldots,m。搭乘地铁需使用武汉通。乘客进站和出站时各刷一次卡,进站时在卡上记录起始站,出站时按卡上记录的起始站和实际出站站之间的距离扣费。设从第 ii 站进站、第 jj 站出站的代价为 cost⁡(i,j)\operatorname{cost}(i,j),则

cost⁡(i,j)=∣i−j∣.\operatorname{cost}(i,j)=|i-j|.

计费与乘车时间无关。在第 ii 站进站,哪怕在地铁上待一整天,从第 jj 站出站仍只需付 cost⁡(i,j)\operatorname{cost}(i,j)。

两人想到一个免费乘车方案。陆仁甲从循礼门、陆仁乙从广埠屯进站,分别坐到途中的螃蟹岬站下车,在站内交换武汉通。随后陆仁甲继续坐到广埠屯,他手上的卡记录的起始站恰好是广埠屯,因此扣费 00 元。同理陆仁乙坐到循礼门后也扣费 00 元。

现在有 nn 个人搭地铁,分别编号为 1,…,n1,\ldots,n。第 ii 个人从第 sis_i 站出发去第 eie_i 站,si≠eis_i\ne e_i,并沿最短路线乘车。

  • 若 si<eis_i<e_i,他的路线依次经过 si,si+1,…,ei−1,eis_i,s_i+1,\ldots,e_i-1,e_i。
  • 若 si>eis_i>e_i,他的路线依次经过 si,si−1,…,ei+1,eis_i,s_i-1,\ldots,e_i+1,e_i。

开始时,所有人都已在自己的起始站刷卡进站,第 ii 个人位于第 sis_i 站。每次可以执行以下两种操作之一。

  • 操作 0 x y 让编号为 xx 的乘客乘车到第 yy 站后下车。第 yy 站必须位于该乘客当前位置至目的站 exe_x 的路线中,且不能等于他的当前位置。1≤x≤n1\le x\le n,1≤y≤m1\le y\le m。
  • 操作 1 x y 让编号为 xx 和 yy 的乘客交换武汉通。两个人此时必须在同一个站。1≤x,y≤n1\le x,y\le n。

一次操作中未提及的人在原地等候。所有操作结束后,第 ii 个人必须在第 eie_i 站,所有人一起刷卡出站。求使所有人的扣费总和最小的乘车方案。

输入格式

第一行一个正整数 TT,表示数据组数。每组数据如下。

  • 第一行两个用空格隔开的正整数 n,mn,m,分别表示人数和地铁站数。
  • 接下来 nn 行,每行两个用空格隔开的正整数 si,eis_i,e_i,分别表示第 ii 个人的起始站和终点站。si≠eis_i\ne e_i,1≤si,ei≤m1\le s_i,e_i\le m。

输出格式

对每组数据输出一个最优方案。若有多个方案的扣费总和都最小,输出任意一个即可。

每组第一行输出两个用空格隔开的非负整数 ans,s\mathrm{ans},s,分别表示最小总扣费和操作数。要求 s≤400000s\le400000。

接下来 ss 行,每行输出三个整数 type x y,分别表示操作类型和两个参数。类型为 00 或 11,x,yx,y 的限制如题目描述。

样例

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

数据范围与约定

对于所有数据,1≤T≤61\le T\le6。

测试点 nn mm
1 =2=2 =1000=1000
2 =100=100 =2=2
3 =4=4 =5=5
4 ≤40\le40 ≤100\le100
5 ≤100\le100 ≤1000\le1000
6
7 ≤2000\le2000 ≤20000\le20000
8
9 ≤60000\le60000 ≤100000\le100000
10 ≤100000\le100000 ≤1000000\le1000000

原作者 VFleaKing 注明这是虚构题设。作者当时实测进站后从原站出站会扣费 1.81.8 元,请勿模仿题中做法。