#P8592. 『JROI-8』颅脑损伤 2.0(加强版)

『JROI-8』颅脑损伤 2.0(加强版)

题目背景

注意到本题特殊的时间限制。

普通版

题目描述

给定 nn 条线段,第 ii 条是 [li,ri][l_i,r_i],将他们染成红色或黑色,要求:

  1. 任意两条红色不相交
  2. 任意一条黑色至少和一条红色相交。

请最小化红色线段的长度和,并输出这个长度和。

一条线段 [li,ri][l_i,r_i] 的长度定义为 rilir_i-l_i,两条线段 [li,ri],[lj,rj][l_i,r_i],[l_j,r_j]当且仅当存在 k[li,ri]k\in[l_i,r_i]k[lj,rj]k\in[l_j,r_j]

输入格式

第一行一行一个正整数,代表 nn

接下来 nn 行,每行两个整数,代表 li,ril_i,r_i,用空格隔开。

输出格式

一行一个非负整数,代表最小的红色线段的长度和。

5
-6 5
1 3
-4 9
-1 10
6 8

4

提示

数据范围

测试点编号 nn\le
1101\sim10 5×1055\times 10^5

对于所有数据,满足 109li<ri109-10^9\le l_i<r_i\le10^9

本题采用捆绑测试。