CF559E Gerald and Path

题意

根线段，已知其中一个端点和长度，求最长覆盖

题解

等价于每根线段要么不选，要么取一段前缀，要求两两无交，求最长覆盖

按已知端点排序， 表示前 条线段，被覆盖的最靠右的点在 或 左侧的最长覆盖
是已知端点， 是向左的另一个端点， 是向右的另一个端点

• 不选
  
• 向右
  如果 左边的线段在 右边有贡献，那么不如不选
  也就是 直接接在最后
  即
• 向左
  如果线段 在 左边有贡献， 在 右边有贡献，那么 向右肯定不劣于向左
  于是可以枚举线段 ， 算 左边的贡献， 全部向右
  即令 ，
  这一块可以优化到单行 ，详见代码

最后，根据定义，

总共

codeforces submission 155923484