E - Segment-Tree Optimization Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N 項からなる数列があり、これから Q 個のクエリが与えられます。 i 番目のクエリでは区間 [L_i, R_i] に対するクエリが与えられます（区間 [a,b] は a 以上 b 以下の整数からなる集合です）。

あなたは、この問題に、下記の条件を満たす二分木を用いて答えます。ただし、以下の記述で i,j,k は整数を表します。

  • 各頂点は区間を持つ
  • 根となる頂点は区間 [1, N] を持つ
  • 区間 [i, i] を持つ頂点は葉である。また、葉が持つ区間は [i,i] と表される
  • 葉でない頂点にはちょうど 2 個の子が存在する。また、葉でない頂点が持つ区間を [i,j] とすると、この頂点の子が持つ区間は [i,k] と [k+1,j] である（i\leq k<j）

この二分木では区間 [L,R] に対するクエリが与えられると、以下の規則で再帰的に探索が行われます。

  1. はじめに、根が調査される
  2. ある頂点が調査されたとき、この頂点の持つ区間が [L, R] に含まれるならば、子孫は調査しない
  3. ある頂点が調査されたとき、この頂点の持つ区間と [L, R] が共通部分を持たないならば、子孫は調査しない
  4. ある頂点が調査されたとき、2,3 のどちらにも当てはまらなければ、子である頂点 2 つを調査する（なお、葉である頂点は必ず 2,3 のどちらかに当てはまることが示せる）

Q 個のクエリに答える時、調査された頂点の深さ（根からの距離）の最大値を d 、深さ d の頂点が調査された回数の総和を c とします。ただし、一つのクエリで複数個の深さ d の頂点が調査された場合、および同じ頂点が複数のクエリで調査された場合にはそれぞれ複数回数えます。

あなたは二分木を適切に設計し、d を最小にしたのち、その範囲内で c を最小にしたいと考えています。このときの 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 つめのクエリについては、頂点 1,2,3,4,5 が調査され、この中で最大の深さは頂点 4,5 の 2
  • 2 つめのクエリについては、頂点 1,2,3,4,5,6,7,8,9 が調査され、この中で最大の深さは頂点 8,9 の 3
  • 3 つめのクエリについては、頂点 1,2,3,4,5,6,7 が調査され、この中で最大の深さは頂点 4,5,6,7 の 2
  • 4 つめのクエリについては、頂点 1,2,3,4,5,8,9 が調査され、この中で最大の深さは頂点 8,9 の 3

となります。したがって、この場合は d=3 であり、深さ 3 の頂点が調査された回数は 2 つめのクエリの際の頂点 8,9 、 4 つめのクエリの際の頂点 8,9 で計 4 回であるため、c=4 となります。実はこれは最適な方法の一例です。

（図の上段が頂点の番号、下段が各頂点が持つ区間です。）

入力例 2

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

出力例 2

4 4

Score : 700 points

Problem Statement

There is a sequence of N terms, and Q queries will be given on this sequence. The i-th query is for the interval [L_i, R_i] (the interval [a,b] is a set of integers between a and b, inclusive).

You will answer this problem using a binary tree that satisfies the following conditions. Here, i,j,k represent integers.

  • Each node has an interval.
  • The root node has the interval [1, N].
  • The node with the interval [i, i] is a leaf. Also, the interval of a leaf can be represented as [i,i].
  • Each non-leaf node has exactly two children. Also, if the interval of a non-leaf node is [i,j], the intervals of the children of this node are [i,k] and [k+1,j] (i\leq k<j).

In this binary tree, when a query for the interval [L,R] is given, a search is performed recursively according to the following rules.

  1. Initially, the root is investigated.
  2. When a node is investigated, if the interval of this node is included in [L, R], its descendants are not investigated.
  3. When a node is investigated, if the interval of this node have no intersection with [L,R], its descendants are not investigated.
  4. When a node is investigated, if neither 2. nor 3. applies, the two child nodes are investigated. (It can be shown that either 2. or 3. always applies to a leaf node.)

When answering Q queries, let d be the maximum depth (distance from the root) of the investigated nodes, and c be the total number of times nodes of depth d are investigated. Here, if multiple nodes of depth d are investigated in a single query, or if the same node is investigated in multiple queries, all those investigations count separately.

You want to design the binary tree to minimize d, and then to minimize c while minimizing d. What are the values of d and c then?

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

Print the integers d and c in question, in this order, separated by a space.

Sample Input 1

6 4
2 3
3 4
2 4
3 3

Sample Output 1

3 4

We have an interval [1,6], and queries for the intervals [2,3],[3,4],[2,4],[3,3]. Here, if you use the binary tree shown in the figure below,

  • for the first query, nodes 1,2,3,4,5 are investigated, and the maximum depth among these is 2 for nodes 4,5;
  • for the second query, nodes 1,2,3,4,5,6,7,8,9 are investigated, and the maximum depth among these is 3 for nodes 8,9;
  • for the third query, nodes 1,2,3,4,5,6,7 are investigated, and the maximum depth among these is 2 for nodes 4,5,6,7;
  • for the fourth query, nodes 1,2,3,4,5,8,9 are investigated, and the maximum depth among these is 3 for nodes 8,9.

Therefore, in this case, d=3, and nodes of depth 3 were investigated four times ー nodes 8,9 in the second query and nodes 8,9 in the fourth query ー so c=4. In fact, this is an optimal method.

(In the figure, the upper row shows the node number, and the lower row shows the interval of each node.)

Sample Input 2

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

Sample Output 2

4 4