Guitar_Jasmine @ 2019-10-10 10:48:47
蒟蒻求助 看了题解都没有解释虚点优化的。。。 又不想打暴力水过（因为觉得自己n^2*m卡不过去）~~~~
by Pluto_Xz @ 2019-10-10 10:52:48
@柳暗花明
除了名字唬人，有什么难理解的地方吗？
你新开一个点连向车站，再把区间连向这个点就相当于这个区间连向个所有车站
by Pluto_Xz @ 2019-10-10 10:53:31
@柳暗花明
不想水这道题建议用线段树优化建边做。
by Guitar_Jasmine @ 2019-10-10 11:02:28
@Pluto_Xz 那是只需要建立一个虚点吗？ 但是这样连边的层次会不会很乱？ 就比如x这个节点第i次被覆盖，虚点向它连一条边，第j次未被覆盖，它又向虚点连了一条边，这样岂不是乱了？ 求dalao详细解释qwq
by Pluto_Xz @ 2019-10-10 11:05:56
@柳暗花明
自己画图模拟一下就可以了，不难懂，也不好解释
by Guitar_Jasmine @ 2019-10-10 11:07:28
@Pluto_Xz 好吧谢谢啦qwq
by lk_liang @ 2019-11-14 19:36:52
@柳暗花明 大佬你A没 能给我解释一下吗。。
by lk_liang @ 2019-11-14 19:38:13
@柳暗花明 感激不尽，，太菜了
by Guitar_Jasmine @ 2019-11-14 20:49:37
@lk_liang 。。。我太菜了QWQ
by Guitar_Jasmine @ 2019-11-14 20:52:00
@lk_liang 最后没抵住诱惑还是暴力水过去了。。。
by lk_liang @ 2019-11-14 20:56:23
@柳暗花明
哈哈哈哈我过了，，
懵出来的思路
我大概解释下
就是对于每趟车次 都建一个虚拟点
这趟车次中 经过不停留的点 连 虚拟点
虚拟点 连 这趟车次中停留的点
所有开了m个虚拟点
一开始我以为只开一个虚拟点
所以还是很简单的