@[codesonic](/space/show?uid=45443) 为什么我想的是$n^2$建边跑最短路呢……这样复杂度也是$n^2$的啊……
by VenusM1nT @ 2018-12-17 11:45:51
这题不是tsp吗哪来的多项式做法啊
by EternalAlexander @ 2018-12-17 11:52:32
允许随机化啊qwq。。。也不用最优，只要很优就行了。。
虽然这个要求好像有点过分
by codesonic @ 2018-12-17 11:58:35
这是一般的tsp问题吧....怎么多项式
by hehelego @ 2018-12-17 11:59:47
如果x,y>0,那这个不就是莫队的两个坐标移动差不多的东西吗
而且窝也没要求最短啊，只需要比较短
by codesonic @ 2018-12-17 12:02:46
比较短？
~~爬山？遗传？模拟退火？~~
by xenonex @ 2018-12-17 12:04:57
@[xenonex](/space/show?uid=86061) 对于膜队玄学的排序方式就是那个啥啊
```cpp
bool cmp(node a,node b){
return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;
}
```
其实如果找到一种更好的排序方法也能改进膜队诶
by codesonic @ 2018-12-17 12:09:02
~~模拟退火辣么好~~
by p_b_p_b @ 2018-12-17 12:33:40
@[codesonic](/space/show?uid=45443) 改进不了，可以证明每次只在一维改变1的情况下复杂度不能小于O(n^(3/2)).
by bzy369258147 @ 2018-12-17 12:38:49
@[codesonic](/space/show?uid=45443) 具体方法是把整个上三角的所有根号分块的顶点全选.这样必须遍历所有的子三角形，所有相邻三角形的距离为O(sqrt(n)),然后有O(sqrt(n) * sqrt(n))个三角形.
by bzy369258147 @ 2018-12-17 12:41:05