【题解】LuoGu4623：BUREK

最新推荐文章于 2020-11-30 21:30:30 发布

原创最新推荐文章于 2020-11-30 21:30:30 发布 · 380 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#题解 #LuoGu #差分 #树状数组

题解同时被 3 个专栏收录

435 篇文章

订阅专栏

LuoGu

255 篇文章

订阅专栏

差分

10 篇文章

订阅专栏

本文介绍了一种判断直线是否穿过三角形的算法，并通过树状数组实现动态更新和查询的功能。利用差分思想，确定直线穿过三角形的条件，再通过树状数组支持动态修改。

原题传送门
直线能穿过三角形，因为直线是平行于坐标轴的，所以很简单
以 $x = p$ 为例

若直线能穿过某一个三角形，那么这条直线必定能穿过三角形的某一条边
换句话说，令三角形三个点中横坐标最小是 $x m i n$ ，最大是 $x m a x$
如果 $x m i n < p < x m a x$ ，直线就能穿过这个三角形

所以可以直接差分， $d_{xmin+1}++,d_{xmax}--$

然后我傻傻的写了树状数组，不过也好，还能支持动态修改

Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n, tree1[maxn << 1], tree2[maxn << 1];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int lowbit(int x){ return x & -x; }
void update1(int x, int y){ for (; x < maxn; x += lowbit(x)) tree1[x] += y; }
void update2(int x, int y){ for (; x < maxn; x += lowbit(x)) tree2[x] += y; }
int query1(int x){ int s = 0; for (; x; x -= lowbit(x)) s += tree1[x]; return s; }
int query2(int x){ int s = 0; for (; x; x -= lowbit(x)) s += tree2[x]; return s; }

int main(){
	freopen("buerk.in", "r", stdin);
	freopen("buerk.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; ++i){
		int xmax = 0, xmin = maxn - 1, ymax = 0, ymin = maxn - 1;
		int x = read(), y = read();
		xmax = max(xmax, x), xmin = min(xmin, x), ymax = max(ymax, y), ymin = min(ymin, y);
		x = read(), y = read();
		xmax = max(xmax, x), xmin = min(xmin, x), ymax = max(ymax, y), ymin = min(ymin, y);
		x = read(), y = read();
		xmax = max(xmax, x), xmin = min(xmin, x), ymax = max(ymax, y), ymin = min(ymin, y);
		update1(xmin + 1, 1), update1(xmax, -1), update2(ymin + 1, 1), update2(ymax, -1);
	}
	int m = read();
	while (m--){
		char c = getchar();
		for (; c != 'x' && c != 'y'; c = getchar());
		int x = read();
		if (c == 'x') printf("%d\n", query1(x));
		else printf("%d\n", query2(x));
	}
	return 0;
}