题目详情题解（0）讨论（0）提交记录（0）

AT_arc168_d.[ARC168D] Maximize Update

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 NN 个格子横向排列，从左到右依次编号为 11 到 NN。最开始，所有格子都是白色。

你可以以任意顺序、任意次数进行以下 MM 种操作：

  • 第 ii 种操作：将第 LiL_i 个格子到第 RiR_i 个格子涂成黑色。

请你求出能够改变格子状态的操作次数的最大值。注意，如果某次操作使得至少有一个格子的颜色发生了变化，则认为该操作改变了格子的状态。

输入格式

输入按以下格式从标准输入给出。

NN MM
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LML_M RMR_M

输出格式

请输出答案。

输入输出样例

  • 输入#1

    3 3
1 3
1 1
3 3

    输出#1

    3

  • 输入#2

    4 3
1 2
3 4
1 4

    输出#2

    2

  • 输入#3

    5 5
4 5
1 1
2 4
1 2
2 5

    输出#3

    4

  • 输入#4

    20 15
2 4
16 19
7 13
1 15
3 18
10 11
1 10
1 7
14 16
1 16
2 17
1 17
12 14
3 17
4 10

    输出#4

    11

说明/提示

限制条件

  • 1≤N≤5001 \leq N \leq 500
  • 1≤M≤N(N+1)21 \leq M \leq \frac{N(N+1)}{2}
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N
  • (Li,Ri)≠(Lj,Rj)(L_i, R_i) \neq (L_j, R_j)（i≠ji \neq j）
  • 输入的所有值均为整数。

样例解释 1

如下操作可以使格子的状态发生变化的操作次数为 33 次。

  • 执行第 22 种操作。第 11 个格子被新涂成黑色。
  • 执行第 33 种操作。第 33 个格子被新涂成黑色。
  • 执行第 11 种操作。第 22 个格子被新涂成黑色。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页