AT_arc164_e [ARC164E] Segment-Tree Optimization

[problemUrl]: https://atcoder.jp/contests/arc164/tasks/arc164_e $ 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\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

題意の $ 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) $ - 入力される値はすべて整数である ### Sample Explanation 1 区間 $ [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 $ となります。実はこれは最適な方法の一例です。 （図の上段が頂点の番号、下段が各頂点が持つ区間です。） !\[\](https://img.atcoder.jp/arc164/c5776dc7ace92d9830788319820bed2d.png)