各客の往来や、人数を調べる \(Q\) 個のクエリを時系列順に並べて、\(Q\) 個のクエリの答えを時刻の早いものから順に求めていく、俗にイベントソートと呼ばれる方法を用います。

つまり、各 \(i = 1, 2, \ldots, N\) について、

• 時刻 \(A_i\) に客 \(i\) が来る
• 時刻 \(B_i+1\) に客 \(i\) が帰る

というイベントが発生し、各 \(i = 1, 2, \ldots, Q\) について、

• 時刻 \(t_i\) での客の人数を求める

というイベントが発生するので、これら \(2N+Q\) 個のイベントを時系列順にソートし、時刻の早いイベントから順に見ていくシミュレーションを行います。 その過程では、現在店内にいる客数をつねに把握しておき、

• 客の往来イベントを処理するごとに客数を更新、
• 人数を調べるイベントを処理するごとにその時点の客数をクエリに対する答えとして記録

していきます。

時間計算量は、\(2N+Q\) 個のイベントを時系列順にソートする操作がボトルネックとなり、\(O((N+Q)\log(N+Q))\) です。

実装の際には、同時刻に複数のイベントが発生する場合のそれらの処理順に注意してください。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, q;
int a[200001], b[200001], t[200001];
int ans[200001];

int main(void)
{
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
  cin >> q;
  for(int i = 1; i <= q; i++) cin >> t[i];
  
  vector<pair<int, int>> vec;
  for(int i = 1; i <= n; i++){
    vec.push_back({a[i], 0});
    vec.push_back({b[i]+1, -1});
  }
  for(int i = 1; i <= q; i++) vec.push_back({t[i], i});
  sort(vec.begin(), vec.end());
  
  int num = 0;
  for(auto p : vec){
    if(p.second == -1) num--;
    else if(p.second == 0) num++;
    else ans[p.second] = num;
  }
  
  for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
  
  return 0;
}