1266 - Points in Rectangle
InputAs the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-ordinates. A point that lies in the boundary of a rectangle is considered inside.
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing an integer q (1 ≤ q ≤ 30000) denoting the number of queries. Each query is either one of the following:
1) 0 x y, meaning that you have got a new point whose co-ordinate is (x, y). But the restriction is that, if a point (x, y) is already listed, then this query has no effect.
2) 1 x1 y1 x2 y2 meaning that you are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).
You can assume that the values of the co-ordinates lie between 0 and 1000 (inclusive).
Output
For each case, print the case number in a line first. Then for each query type (2), you have to answer the number of points that lie inside that rectangle. Print each of the results in separated lines.
Sample Input |
Output for Sample Input |
| 190 1 10 2 6
1 1 1 6 6 1 2 2 5 5 0 5 5 1 0 0 6 5 0 3 3 0 2 6 1 2 1 10 10 |
Case 1:202
3 |
Note
Dataset is huge, use faster I/O methods.
题目类型：二维树状数组
算法分析：由于题目中点的坐标最大值<=1000，所以可以直接使用二维树状数组存图，再维护一个布尔数组hasval[x][y]表示(x,y)处是否有点，如果有则不进行UpDate操作，反之则UpDate，每次直接查询矩阵中有多少点即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 1600; int ans[maxn][maxn]; bool hasval[maxn][maxn]; int lowbit (int val) { return val & (-val); } void UpDate (int x, int y, int val) { while (x <= maxn) { int temp = y; while (temp <= maxn) { ans[x][temp] += val; temp += lowbit (temp); } x += lowbit (x); } } int Query (int x, int y) { int sum = 0; while (x > 0) { int temp = y; while (temp > 0) { sum += ans[x][temp]; temp -= lowbit (temp); } x -= lowbit (x); } return sum; } int main() { // freopen ("aaa.txt", "r", stdin); int t, flag = 1; scanf ("%d", &t); while (t--) { printf ("Case %d:\n", flag++); memset (ans, 0, sizeof (ans)); memset (hasval, false, sizeof (hasval)); int q; scanf ("%d", &q); int i, cmd; for (i = 0; i < q; i++) { scanf ("%d", &cmd); if (cmd == 0) { int x, y; scanf ("%d%d", &x, &y); x++, y++; if (!hasval[x][y]) { UpDate (x, y, 1); hasval[x][y] = true; } } else { int x1, x2, y1, y2; scanf ("%d%d%d%d", &x1, &y1, &x2, &y2); x1++, x2++, y1++, y2++; printf ("%d\n", Query (x2, y2) + Query (x1 - 1, y1 - 1) - Query (x1 - 1, y2) - Query (x2, y1 - 1)); } } } return 0; } |
- « 上一篇：lightoj1259
- lightoj1294：下一篇 »