分数: 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] ,根据以下规则递归执行搜索。
- 首先,调查根源。
- 考察某个节点时,如果该节点的区间包含在 [L, R],其后代不被调查。
- 当考察一个节点时,如果该节点的区间与 [L,R],其后代不被调查。
- 当调查节点时,如果 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