[bzoj4991]-[Usaco2017 Feb]Why Did the Cow Cross the Road III P

cdq写起来真的轻松

题目(BZOJ)

题目(洛谷)

 

这题就是cdq分治裸题……

根据题目,设ai为i点在一边的位置,bi为i点在另一边的位置,可以建立三个偏序关系:

①abs(a-b)>k

②ai<aj

③bi>bj

①可以预处理出;②和③就直接搞cdq分治了…

 

发表评论