A Most Popular Matcha’s Snow Land (Easy)

2 secs 1024 MB
matcharate12's icon matcharate12

問題

GreenTea 王国には、”Matcha’s Snow Land” といういつ行っても行列ができるほど人気な遊園地があります。その遊園地は、このご時世なので来る前に必ず予約をしなければ入れないシステムとなっています。そんな遊園地でクリスマスの昼頃、matcharate君はアルバイトをしていました。

今月のmatcharate君のタスクは、予約が最も殺到している日の区間を調べることです。今、ここに NN 日間の予約の管理表があります。上司のError君によると、MM 人の予約があり、i (1iM)i\ (1\le i\le M) 人目は AiA_i 日目から BiB_i 日目までの予約を受け取っていることが分かっているようです。ここで前述した通り人気なので、11 人の予約あたりで必ず 22 日以上の予約が入ります。この情報から、Error君が出した次の質問に QQ 回だけ答えてください。

  • 予約管理表において、 LjL_j 日目から RjR_j 日目までに予約された1日の予約数の最大値 KK として、1日に KK 個の予約が入っている日数はいくつありますか?

入力・制約

N MN\ M
A1 B1A_1\ B_1
\vdots
AM BMA_M\ B_M
QQ
L1 R1L_1\ R_1
\vdots
LQ RQL_Q\ R_Q

2N,M1052\le N,M\le 10^5
1Ai<BiN1\le A_i\lt B_i\le N
1Q3001\le Q\le 300
1Lj<RjN (1jQ)1\le L_j\lt R_j\le N\ (1\le j\le Q)

出力

QQ 行出力せよ。jj 行目には jj 個目の質問の答えを出力せよ。

入出力例

入力例1
10 5
1 4
3 6
9 10
2 7
8 10
3
1 5
2 8
1 7
出力例1
2
2
2
  • 11 人目では 11 日目から 44 日目までの予約を
  • 22 人目では 33 日目から 66 日目までの予約を、
  • 33 人目では 99 日目から 1010 日目までの予約を、
  • 44 人目では 22 日目から 77 日目までの予約を、
  • 55 人目では 88 日目から 1010 日目までの予約を入れました。

最終的に管理表には 11 日目から順に (1,2,3,3,2,2,1,1,2,2)(1,2,3,3,2,2,1,1,2,2) と書かれます。ここで各要素は k (1kN)k\ (1\le k\le N) 日目に入っている予約数を表します。

よって例えば 11 つ目の質問において、11 日目から 55 日目までの区間で 11 日の最大予約人数は 3(=K)3(=K) 人です。3,43,4 日目の 22 日間が 3(=K)3(=K) 人だけ予約をされているので、22 を出力します。

Submit


Go (1.21)