苏格兰场逃脱记

1309909-20180123095924037-1618037447.png

Mr.x作为大名鼎鼎的嫌犯,想要逃脱本市的探员的追捕。知道这个城市有很多个站点,如上图的X市,圆点为地点,线为两点之间到达的方式,虚线为步行,实线为地铁。Mr.x其实非常希望两个地点尽量有地铁通达,否则自己走路实在是耗费时间。好在Mr.x的哥们神通广大,能说服市政将两个地点间的通行方式改为地铁,但有一个要求,不同的地铁线路之间不能相连,只能以步行方式走过。就如上图那样,从N点到A点,要经过三条不同的地铁线路(N~L,H~C,A)。

实话说了吧,Mr.x先生就是个大路痴,所以他才希望两点之间有地铁通达,这样就不用冒着走错路的风险了——地铁坐反了那又另当别论。总之Mr.x希望现在从N到A点只有一条线路就行了。

于是Mr.x依照本市地图,重新画了一张合适自己的地图,小绿框内就是每条地铁线路可以通达的区域。

1309909-20180123095955350-1680422636.png

也就是希望最终变成下面这样,遵循从北向南连,每个北边的点最多只能向自己可以通达的南边的点连一条地铁线路。变重意味着从步行路变为地铁线路,变轻意味着从地铁线路变为步行线路。

1309909-20180123101901740-2118178734.png

对于原图需要经过的第一条地铁线路,哥们先用一种稀奇古怪的方法把N站点弄到这条线路最北边去了。据说这种方法叫splay,嗯,探员们还不知道这种方法,他们估计连dfs都不会。所以Mr.x毫无需担心。由于之前说到的,北边的地点,对于自己可以通达的南边的站点来说,最多只能有一条地铁线路,所以从N到O的地铁线路被无情摧毁了。

不过据说O是探员的秘密街头点,让他变得交通闭塞一点并无害处。有些探员确实需要锻炼身体了,那些20岁出头的探员还没有30多岁的Mr.x身体敏捷。

1309909-20180123110136115-1112016464.png

但这样从N到I的地铁线路还是没有打通。别急别急,Mr.x的哥们先到地铁考察了一段时间,认为为了尽量缩短距离,有必要把I地点也移到北边去,碍事的K的站点就一边交通闭塞去,一边凉快去吧。听说K地点是Mr.x的朋友Mr.y家所在地。算了,Mr.y也一边凉快去吧。

于是城市线路图就成了下面这样。M站点的人安慰K站点和O站点的人:我从来就没连上地铁线路过,不一样过得……村里的希望出去就没回来了!”

1309909-20180123110156272-1242463729.png

现在要处理H所在的地铁线路。叫哪个地点一边凉快去好呢?H要当最北边的站点,那么J,就决定是你了。听说J是Mr.x女朋友所在地。别呀,J,你回来啊,之前有地铁线路还可以说坐地铁是为了地铁比开车快,下次来看你我就得自己开车——开那辆几年的自行车去看了,一切都暴露了!这比探员还难防!

1309909-20180123110209772-2057141058.png

不论怎样,神通广大的哥们让J地点成为了地铁线路改革的牺牲品。下面最后一步,A站点来了!把A站点先在自己线路玩到最北边,再拉过来作为H的北边站点,大功告成!

1309909-20180123110213709-49169640.png

怎样让一个站点成为最北边的站点呢?答案是先像上面这样,连成一条统一的地铁线路,再从自己使用那个稀奇古怪的方法从上到下一层一层往上拉自己——这就是那位神通广大的哥们的错了,帮站点不能帮到底吗?——所以站点为了标榜自己的正统性,必须改动自己作为南边站点的劣根性,再反转自己。

怎样访问一条指定路径的x-y函数呢?先把x作为最北边的节点,再把y像上面那样连到y,再splay掉。

如何连x到y的边呢?先把x弄到最北边,再让y成为x的北边。x也太辛苦了,每次都推到最北边,还要忍受y还在北边的命运。这可让x站点太感受命运的不公了,凭什么y站点就要在自己的最北边?

如何删x到y的边呢?一样把x弄到最北边,不过现在就可以唆使x不认他的北边节点Y了,X没了北边节点,Y也只好忍痛割舍。不过谁知道Y还有没有其它的南方节点,Y是不是装出来的呢?

至于QTree1,把边权转换为点权,即你经过路线的时候不要钱,但经过某个站点的时候收费。是不是很像黑社会受过路费?Mr.x也无可奈何啊。谁叫转换这么鬼畜?只需南边的地点有过路费,而不许北边的点有?

要是用树链剖分,还需要val[n+i]= ,真是欺人太甚!那多出来的n个点什么事也没做,既不在载客人,也不要接受例行检测,过路费倒是全叫他们收取了!

 

Leave a Reply