官方题解

题目大意

有 $n$ 家公司和 $m$ 为求职者，每家公司有两个能力要求，每位求职者也有两个能力值，求职者只有都满足这两个要求才可以通过面试，求每位求职者可以通过多少家公司的面试。

题目思路

我们可以把两个能力值看成一个二维的坐标，那么对于某家公司的要求 $(a,b)$ ，能力值为 $(x,y)$ 的求职者只有同时满足 $x\geq a$ 且 $y\geq b$ 才可以通过面试，即 $(x,y)$ 在左上角为 $(a,b)$ 到右下角为 $(1000,1000)$ 的范围内即可满足条件。

所以我们不妨用二维差分+前缀和的思想来求出每位求职者可以通过面试的公司数量，对每家公司的要求 $(a,b)$ 点上的差分数组加一，最后求出前缀和，$O(1)$ 查询每位求职者的可通过面试数量。

时间复杂度 $O(10^6)$

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int a[N][N];

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        a[x][y]++;
    }
    
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }

    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        cout<<a[x][y]<<endl;
    }
}