巅峰赛#25 T2

先用暴力进行进行模拟后，我们会发现超时？
那么我们观察数据，a_i.c与a_i.v都是小于等于1000的
这提示了我们可以用值进行模拟
运用二维前缀和计算小于i且j的公司数量
二维前缀和公式：

pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
然后输出即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];//小于i且j的公司数量
struct ikun{
	int c,v;
};
int n,m;
ikun a[1000010],b[1000010];
bool cmp(ikun a,ikun b){
	if(a.c==b.c)return a.c<b.c;
    return a.v<b.v;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int c,v;
    	cin>>c>>v;
        dp[c][v]++;
    }
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            dp[i][j]=dp[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
        	//cout<<dp[i][j]<<' ';
        }
        //cout<<endl;
    }
    for(int i=1;i<=m;i++){
        int c,v;
    	cin>>c>>v;
        cout<<dp[c][v]<<'\n';
    }
}