← 返回题目列表

AtCoder · arc164_e

E. 线段树优化

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

有一个序列 N 条款,以及 将对此序列给出 Q 查询。的 i-第一个查询针对间隔 [L_i, R_i] (间隔 [a,b] 是一组介于 a 和 b,包括)。

您将使用满足以下条件的二叉树来回答此问题。在这里, i,j,k 代表整数。

  • 每个节点都有一个区间。
  • 根节点有区间 [1, N].
  • 具有区间的节点 [i, i] 是一片叶子。另外,叶子的间隔可以表示为 [i,i].
  • 每个非叶节点恰好有两个子节点。另外,如果非叶子节点的间隔为 [i,j],该节点的子节点的间隔为 [i,k] 和 [k+1,j] (i\leq k<j).

在这棵二叉树中,当查询区间 给定 [L,R] ,根据以下规则递归执行搜索。

  1. 首先,调查根源。
  2. 考察某个节点时,如果该节点的区间包含在 [L, R],其后代不被调查。
  3. 当考察一个节点时,如果该节点的区间与 [L,R],其后代不被调查。
  4. 当调查节点时,如果 2. 和 3. 都不适用,则调查两个子节点。 (可以证明 2. 或 3. 始终适用于叶节点。)

接听时 Q 查询,让 d 是所研究节点的最大深度(距根部的距离),并且 c 为深度节点的总次数 d 进行了调查。这里,如果深度的多个节点 d 在单个查询中进行调查,或者如果在多个查询中调查同一节点,则所有这些调查都单独计数。

您想要设计二叉树以最小化 d,然后最小化 c 同时最小化 d。的价值观是什么 d 和 c 然后呢?

约束

  • 2\leq N \leq 4000
  • 1\leq Q \leq 10^5
  • 1\leq L_i \leq R_i \leq N (1\leq i \leq Q)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

输出

打印整数 d 和 c 有问题,按此顺序,用空格分隔。


示例输入 1

6 4
2 3
3 4
2 4
3 3

示例输出 1

3 4

我们有一个间隔 [1,6],并查询间隔 [2,3],[3,4],[2,4],[3,3]。这里,如果使用下图所示的二叉树,

  • 对于第一个查询,节点 1,2,3,4,5 进行了研究,其中最大深度是 2 对于节点 4,5;
  • 第二个查询,节点 1,2,3,4,5,6,7,8,9 进行了研究,其中最大深度是 3 对于节点 8,9;
  • 对于第三个查询,节点 1,2,3,4,5,6,7 进行了研究,其中最大深度是 2 对于节点 4,5,6,7;
  • 对于第四个查询,节点 1,2,3,4,5,8,9 进行了研究,其中最大深度是 3 对于节点 8,9.

因此,在这种情况下, d=3,以及深度节点 3 共调查四次——节点 8,9 第二个查询和节点 8,9 在第四次查询中——所以 c=4。事实上,这是一个最优的方法。

(图中上行显示节点编号,下行显示每个节点的间隔。)


示例输入 2

12 6
1 10
2 7
3 6
4 9
5 8
11 12

示例输出 2

4 4