一閃一閃亮晶晶，滿天都是小星星，牛牛晚上閑來(lái)無(wú)聊，便躺在床上數(shù)星星。

牛牛把星星圖看成一個(gè)平面，左上角為原點(diǎn)(坐標(biāo)為(1, 1))。現(xiàn)在有n顆星星，他給每顆星星都標(biāo)上坐標(biāo)(x_i，y_i)，表示這顆星星在第x行，第y列。

現(xiàn)在，牛牛想問(wèn)你m個(gè)問(wèn)題，給你兩個(gè)點(diǎn)的坐標(biāo)(a1, b1)(a2，b2)，表示一個(gè)矩形的左上角的點(diǎn)坐標(biāo)和右下角的點(diǎn)坐標(biāo)，請(qǐng)問(wèn)在這個(gè)矩形內(nèi)有多少顆星星（邊界上的點(diǎn)也算是矩形內(nèi)）。

輸入描述:

第一行輸入一個(gè)數(shù)字n(1≤n≤100000)，表示星星的顆數(shù)。
接下來(lái)的n行，每行輸入兩個(gè)數(shù)x和y(1≤xy≤1000），表示星星的位置。 然后輸入一個(gè)數(shù)字m(1≤m≤100000), 表示牛牛詢問(wèn)問(wèn)題的個(gè)數(shù)。
接下來(lái)m行，每行輸入四個(gè)數(shù)字a1，b1，a2，b2(1≤a1＜a2≤1000), (1≤b1＜b2≤1000）
題目保證兩顆星星不會(huì)存在于同一個(gè)位置。

輸出描述:

輸出一共包含m行，每行表示與之對(duì)應(yīng)的每個(gè)問(wèn)題的答案。 示例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

蠻力法超過(guò)了時(shí)間限制
只有使用二維前綴來(lái)進(jìn)行矩陣和降維，在O（1）的時(shí)間內(nèi)計(jì)算出星星的個(gè)數(shù)。

#include <iostream> #include <vector> using namespace std;int main() {int n;cin >> n;vector<vector<int>> tbl(1001, vector<int>(1001, 0));vector<vector<int>> sum(tbl);int x, y;for (int i = 0; i < n; ++i){cin >> x >> y;tbl[x][y] = 1;}for (int i = 1; i < 1001; ++i){for (int j = 1; j < 1001; ++j){sum[i][j] = tbl[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];}}int m;cin >> m;int ax, ay, bx, by;for (int i = 0; i < m; ++i){cin >> ax >> ay >> bx >> by;int count = sum[bx][by] + sum[ax-1][ay-1] - sum[bx][ay-1] - sum[ax-1][by];cout << count << endl;}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/immjc/p/9229772.html

總結(jié)

以上是生活随笔為你收集整理的[NowCoder] 牛牛数星星的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。