谷甚论卡常
查看原帖
谷甚论卡常
361308
Stinger楼主2021/1/12 20:41

萌新刚学卡常,求助(((

反正只是卡常就懒得打注释了

#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;
}
2021/1/12 20:41
加载中...