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
| #include<cstdio> #include<algorithm>
const int MAXN = 500000 * 5 + 5;
struct node { int x, y, type, add, id, ans; } a[MAXN], tmp[MAXN];
int n, m, newp; int ans[MAXN];
void add (int x, int y, int type, int add, int id, int ans) { a[++newp] = (node){x, y, type, add, id, ans}; }
bool cmp1 (node x, node y) { if (x.x == y.x) { if (x.y == y.y) { return x.type < y.type; } return x.y < y.y; } return x.x < y.x; }
void cdq (int l, int r) { if (l == r) { return; } int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r); int newl = l, newr = mid + 1, pos = l, ans = 0; while (newl <= mid && newr <= r) { if (a[newl].y <= a[newr].y) { if (a[newl].type == 1) { ++ans; } tmp[pos++] = a[newl++]; } else { if (a[newr].type == 2) { a[newr].ans += ans; } tmp[pos++] = a[newr++]; } } while (newl <= mid) { tmp[pos++] = a[newl++]; } while (newr <= r) { if (a[newr].type == 2) { a[newr].ans += ans; } tmp[pos++] = a[newr++]; } for (int i = l; i <= r; ++i) { a[i] = tmp[i]; } }
int main (void) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y, 1, 0, 0, 0); } for (int i = 1; i <= m; ++i) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); add(x2, y2, 2, 1, i, 0); add(x1 - 1, y2, 2, -1, i, 0); add(x2, y1 - 1, 2, -1, i, 0); add(x1 - 1, y1 - 1, 2, 1, i, 0); } std::sort(a + 1, a + 1 + newp, cmp1); cdq(1, newp); for (int i = 1; i <= newp; ++i) { if (a[i].type == 2) { ans[a[i].id] += a[i].add * a[i].ans; } } for (int i = 1; i <= m; ++i) { printf("%d\n", ans[i]); } return 0; }
|