Distance

题目链接:https://www.nowcoder.com/acm/contest/16/B

TGSteven大佬说是智障题,所以我成了智障了。。。

整场比赛就写了1,2题,而且这题还是最后做出来的。

如果没有绝对值,无疑是大水题。

然后有绝对值的话,只用分类讨论即可。

可以维护四个val,分别代表不同情况下前面的影响。

我加了w的排序,少了两个val的维护。

比如在i插入了一个值w,那么此时线段树中只含比他小的值,那么只有考虑id的影响,

对于在i之前的点,就是wi^2 +i^2 - wj^2 - j^2,对于在i之后的点就是 wi^2 + j^2 - i^2 - wj^2。

取max搞定。

c++代码如下:

 

4 + 8 =