NC16581. 牛牛数星星
描述
输入描述
第一行输入一个数字n(1≤n≤100000)，表示星星的颗数。
接下来的n行，每行输入两个数xi和yi(1≤xi，yi≤1000），表示星星的位置。
然后输入一个数字m(1≤m≤100000), 表示牛牛询问问题的个数。
接下来m行，每行输入四个数字a1，b1，a2，b2(1≤a1＜a2≤1000), (1≤b1＜b2≤1000）
题目保证两颗星星不会存在于同一个位置。
输出描述
输出一共包含m行，每行表示与之对应的每个问题的答案。
示例1
输入:
4 1 1 2 2 3 3 1 3 4 1 1 2 2 1 1 3 3 2 2 3 3 1 2 2 3
输出:
2 4 2 2
C++(clang++ 11.0.1) 解法, 执行用时: 80ms, 内存消耗: 8720K, 提交时间: 2022-09-19 20:27:25
#include<iostream>
const int N = 1010;
int n,m,q,x;
int a[N][N],s[N][N];
int main()
{
scanf("%d",&x);
for(int i=1;i<=x;++i)
{
scanf("%d%d",&n,&m);
a[n][m]++;
}
for(int i=1;i<=1000;++i){
for(int j=1;j<=1000;++j){
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
scanf("%d",&q);
while(q--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
}
return 0;
}