『JROI-8』颅脑损伤 2.0（加强版）

Luogu

IDLGP8592

Time500ms

Memory128MB

DifficultyP5

洛谷原创O2优化洛谷月赛

给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$，将他们染成红色或黑色，要求： 1. 任意两条红色不相交 2. 任意一条黑色**至少**和一条红色相交。请最小化红色线段的长度和，并输出这个长度和。一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交**当且仅当**存在 $k\in[l_i,r_i]$ 且 $k\in[l_j,r_j]$。 ## Input 第一行一行一个正整数，代表 $n$。接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。 ## Output 一行一个非负整数，代表最小的红色线段的长度和。 [samples] ## Background 注意到本题特殊的时间限制。 [普通版](https://www.luogu.com.cn/problem/P8591)。 ## Note **数据范围** |测试点编号|$n\le$| | :----------: | :----------: | |$1\sim10$|$5\times 10^5$| 对于所有数据，满足 $-10^9\le l_i<r_i\le10^9$。本题采用捆绑测试。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "『JROI-8』颅脑损伤 2.0（加强版）",
    "description": {
      "content": "给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$，将他们染成红色或黑色，要求： 1. 任意两条红色不相交 2. 任意一条黑色**至少**和一条红色相交。 请最小化红色线段的长度和，并输出这个长度和。 一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交**当且仅当**存在 $k\\in[l_i,r_i]$ 且",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8592"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$，将他们染成红色或黑色，要求：\n\n1. 任意两条红色不相交\n2. 任意一条黑色**至少**和一条红色相交。\n\n请最小化红色线段的长度和，并输出这个长度和。\n\n一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交**当且仅当**存在 $k\\in[l_i,r_i]$ 且...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments