方法一 暴力

将每辆巴士的服务范围存储起来, 再遍历得到服务某城市的巴士数量.
c++10ms, 时间限制以及测试数据都太宽松, 暴力完全没有问题
单次测试数据的时间复杂度为O(N*P)

//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<pair<int, int>> bars;

    int T, N, P, C;
    int l, r;
    int i, j, k;
    int count;
    cin >> T;
    for(i=1; i<=T; i++)
    {
        cin >> N;
        for(j=0; j<N; j++)
        {
            cin >> l >> r;
            bars.emplace_back(l, r);
        }

        cin >> P;
        cout << "Case #" << i << ":";
        while(P--)
        {
            count = 0;
            cin>> C;
            for(auto p : bars)
            {
                if(C>=p.first && C<=p.second)
                    count++;
            }
            cout << " " << count;
        }

        bars.clear();
        cout << endl;
    }

    return 0;
}

更为巧妙的方法

我们是否能通过所有巴士的服务范围而直接得到任何一座城市的巴士数量呢
对一段序列{0, 0, 0, 0, 0}, 如果我们想让它第二到第四个元素都加个1, 我们可以让第二个元素+1, 第五个元素-1,
得到{0, 1, 0, 0, -1}, 再执行seq[i] = seq[i]+seq[i-1], 就可以得到{0, 1, 1, 1, 0}. 这种变化是线性传递的, 2处的变化和5处的变化相互抵消, 从而2的变化只影响了[2, 5)

如下代码c++6ms, 面对较大数据时表现较好

//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>

using namespace std;

int main() {
    int count[5010];
    int T, N, P, C;
    int i, j, k;
    int l, r;

    cin >> T;
    for(i=1; i<=T; i++)
    {
        for(j=1; j<5001; j++)
            count[j] = 0;
        cin >> N;
        for(j=0; j<N; j++)
        {
            cin>> l >> r;
            count[l]++;
            count[r+1]--;
        }

        for(j=2; j<=5001; j++)
            count[j] += count[j-1];

        cin >> P;
        cout << "Case #" << i << ":";
        while(P--)
        {
            cin >> C;
            cout << " " << count[C];
        }

        cout << endl;
    }

    return 0;
}