BZOJ1935或洛谷2163 [SHOI2007]园丁的烦恼

BZOJ原题链接

洛谷原题链接

很容易想到二维前缀和。

设\(S[i][j]\)表示矩阵\((0, 0)(i, j)\)内树木的棵数，则询问的矩形为\((x, y)(xx, yy)\)时，答案为\(S[xx][yy] - S[x - 1][yy] - S[xx][y - 1] + S[x - 1][y - 1]\)。

但这题坐标极大，显然不能直接求。

对\(x,y\)都进行离散化，然后我们考虑求询问。

将询问的矩阵拆成二维前缀和计算形式的四个矩阵，这样就可以用扫描线快速求矩阵，并统计答案即可。

这里我是用树状数组来维护的。

因为偷懒就用了\(vector\)

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

const int N = 5e5 + 10;

struct dd {

	int x, y, xx, yy;

};

dd a[N];

int tr_x[N], tr_y[N], ls_x[N << 2], ls_y[N << 2], C[N], an[N], nl, ml, xl, yl;

vector<int>X[N], q_1[N], q_2[N];

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline int lowbit(int x) { return x & -x; }

inline void add(int x)

{

	for (; x <= ml; x += lowbit(x))

		C[x]++;

}

inline int ask(int x)

{

	int s = 0;

	for (; x; x -= lowbit(x))

		s += C[x];

	return s;

}

inline int BSX(int x)

{

	int l = 1, r = nl, mid;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (!(ls_x[mid] ^ x))

			return mid;

		ls_x[mid] > x ? r = mid - 1 : l = mid + 1;

	}

	return 0;

}

inline int BSY(int x)

{

	int l = 1, r = ml, mid;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (!(ls_y[mid] ^ x))

			return mid;

		ls_y[mid] > x ? r = mid - 1 : l = mid + 1;

	}

	return 0;

}

int main()

{

	int i, j, n, m, L;

	n = re();

	m = re();

	for (i = 1; i <= n; i++)

	{

		tr_x[i] = re() + 1;

		tr_y[i] = re() + 1;

		ls_x[++xl] = tr_x[i];

		ls_y[++yl] = tr_y[i];

	}

	for (i = 1; i <= m; i++)

	{

		a[i].x = re();

		a[i].y = re();

		a[i].xx = re() + 1;

		a[i].yy = re() + 1;

		ls_x[++xl] = a[i].x;

		ls_x[++xl] = a[i].xx;

		ls_y[++yl] = a[i].y;

		ls_y[++yl] = a[i].yy;

	}

	sort(ls_x + 1, ls_x + xl + 1);

	sort(ls_y + 1, ls_y + yl + 1);

	ls_x[xl + 1] = ls_y[yl + 1] = -1;

	for (i = 1; i <= xl; i++)

		if (ls_x[i] ^ ls_x[i + 1])

			ls_x[++nl] = ls_x[i];

	for (i = 1; i <= yl; i++)

		if (ls_y[i] ^ ls_y[i + 1])

			ls_y[++ml] = ls_y[i];

	for (i = 1; i <= n; i++)

		X[BSX(tr_x[i])].push_back(BSY(tr_y[i]));

	for (i = 1; i <= m; i++)

	{

		a[i].y = BSY(a[i].y);

		a[i].yy = BSY(a[i].yy);

		q_1[BSX(a[i].x)].push_back(i);

		q_2[BSX(a[i].xx)].push_back(i);

	}

	for (i = 1; i <= nl; i++)

	{

		for (j = 0, L = X[i].size(); j < L; j++)

			add(X[i][j]);

		for (j = 0, L = q_1[i].size(); j < L; j++)

			an[q_1[i][j]] += ask(a[q_1[i][j]].y) - ask(a[q_1[i][j]].yy);

		for (j = 0, L = q_2[i].size(); j < L; j++)

			an[q_2[i][j]] += ask(a[q_2[i][j]].yy) - ask(a[q_2[i][j]].y);

	}

	for (i = 1; i <= m; i++)

		printf("%d\n", an[i]);

	return 0;

}

巴特西

BZOJ1935或洛谷2163 [SHOI2007]园丁的烦恼

BZOJ原题链接

洛谷原题链接

最新文章

热门文章