2020牛客多校第二场H-Happy Triangle


\(对查询的边x,分为两种情况 \)

\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)

\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)

\(可用平衡树或线段树进行维护,此处用动态开点线段树来解决 \)

\(区间[l, r]权值为min_{x_i \in [l, r]}\{x_i-x_{i-1}\} \)


 

发表评论