P2070 刷墙

  一开始以为是离散化线段树,交了两次发现做不了,因为对于一个离散化后线段树上的点,其单点权值>=2,并不能知道应该取这个点和左边的点构成的线段,还是这个点和右边的点构成的线段。

  其实正解很简单,就是个前缀和……

  对于左端点为1,右端点为-1。排序之后,从左到右前缀和。这样如果现在的前缀和>1,说明至少有两条线段延伸到这个点,那么这个点和上一个点之间的线段至少被经过了两次,那么直接加上这段长度即可。

  代码太短……不贴了 >///<

原文地址:https://www.cnblogs.com/popo-black-cat/p/10852915.html