萌新刚学卡常,求助(((
反正只是卡常就懒得打注释了
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)
char buf[131072], *p1 = buf, *p2 = buf;
inline int read() {
char ch;
int x(0);
while ((ch = gc) < 48);
do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
return x;
}
const int N = 2500005;
struct Question {
int id, f, x, y;
inline bool operator < (const Question X) const {return x < X.x;}
} q[N];
struct Node {
int id, v;
inline bool operator < (const Node x) const {return v < x.v;}
} b[N];
struct Point {
int x, y;
inline bool operator < (const Point X) const {return x < X.x;}
} p[N];
int x[N], y[N], ans[N], c[N], C[N], D[N], n, M;
inline void upd(const int x) {
for (int i(x); i <= n + M; i += (i & ~i + 1)) ++ c[i];
}
inline int query(const int x) {
int sum(0);
for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
return sum;
}
inline void initialization(int *A, int *C) {
for (int i(1); i <= n; ++ i) b[i].id = i, b[i].v = A[i];
for (int i(n + 1); i <= n + M; ++ i) b[i].id = i, b[i].v = C[i - n];
std::sort(b + 1, b + n + M + 1);
if (b[1].id <= n) A[b[1].id] = 1;
else C[b[1].id - n] = 1;
for (int i(2); i <= n + M; ++ i)
if (b[i].id <= n)
if (b[i - 1].id <= n)
A[b[i].id] = A[b[i - 1].id] + (b[i].v == b[i - 1].v ? 0 : 1);
else A[b[i].id] = C[b[i - 1].id - n] + (b[i].v == b[i - 1].v ? 0 : 1);
else
if (b[i - 1].id <= n)
C[b[i].id - n] = A[b[i - 1].id] + (b[i].v == b[i - 1].v ? 0 : 1);
else C[b[i].id - n] = C[b[i - 1].id - n] + (b[i].v == b[i - 1].v ? 0 : 1);
}
int main() {
int m, k(1);
scanf("%d%d", &n, &m);
for (int i(1); i <= n; ++ i) x[i] = read(), y[i] = read();
for (int i(1); i <= m; ++ i) {
int a(read()), b(read()), c(read()), d(read());
C[++ M] = a - 1, D[M] = b - 1, q[M].id = i, q[M].f = 1;
C[++ M] = c, D[M] = d, q[M].id = i, q[M].f = 1;
C[++ M] = a - 1, D[M] = d, q[M].id = i, q[M].f = -1;
C[++ M] = c, D[M] = b - 1, q[M].id = i, q[M].f = -1;
}
initialization(x, C), initialization(y, D);
for (int i(1); i <= M; ++ i) q[i].x = C[i], q[i].y = D[i];
for (int i(1); i <= n; ++ i) p[i] = Point{x[i], y[i]};
std::sort(p + 1, p + n + 1);
for (int i(1); i <= n; ++ i) x[i] = p[i].x, y[i] = p[i].y;
std::sort(q + 1, q + M + 1);
for (int i(1); i <= M; ++ i) {
while (k <= n && x[k] <= q[i].x) upd(y[k ++]);
ans[q[i].id] += q[i].f * query(q[i].y);
}
for (int i(1); i <= m; ++ i) printf("%d\n", ans[i]);
return 0;
}