自动搬运

查看原文

来自洛谷，原作者为

	Inui_Sana ばか！へんたい！うるさい！⠀

搬运于2025-08-24 22:02:03，当前版本为作者最后更新于2022-05-22 13:48:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

解题思路：桶+差分

看到题解好多大奆都用树状数组，扫描线什么的完全不会啊。但这题其实可以用简单的桶数组来解决。代码量小，时间短。

Part 1 暴力

最简单的想法，对于每条直线，找哪些三角形满足条件。时间复杂度 $O(nm)$。能拿30pts。

Part 2 桶优化

接下来就要思考如何在 $O(1)$ 的时间内得到一条直线穿过多少三角形。桶能够很好地满足这个需求。再看数据范围，$0 \le x_1,y_1,x_2,y_2,x_3,y_3 < 10^6$，可以说完美适于桶。

设置两个桶 $boxx$ 和 $boxy$，分别用来存储直线 $x=i$ 和 $y=i$ 穿过的三角形数量。对于每个三角形，求出三个点中最大和最小的 $x$ 坐标和 $y$ 坐标，将 $boxx[(x_{min},x_{max})]$ 和 $boxy[(y_{min},y_{max})]$ 都 $+1$。对于每条直线，直接输出答案即可。时间复杂度 $O(n^2)$。

Part 3 差分维护桶

很容易发现，对于每个三角形，总是在一段区间内 $+1$。所以可以用差分维护。对于每个三角形，将 $boxx[x_{min}+1]$ 和 $boxy[y_{min}+1]$ 都 $+1$，$boxx[x_{max}]$ 和 $boxy[y_{max}]$ 都 $-1$。最后再还原即可。时间复杂度 $O(n)$。（但其实还原差分数组要进行 $10^6$ 次）

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000007;
int n,m,boxx[maxn],boxy[maxn];
int main(){
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<=n;i++){
		int maxx=-1*(1e9+7),maxy=-1*(1e9+7),minx=1e9+7,miny=1e9+7;
		for(int j=1;j<=3;j++){
			scanf("%d%d",&x,&y);
			maxx=max(maxx,x);maxy=max(maxy,y);
			minx=min(minx,x);miny=min(miny,y);
		}
		boxx[minx+1]++;boxy[miny+1]++;
		boxx[maxx]--;boxy[maxy]--;
	}
	for(int i=1;i<=1000000;i++){
		boxx[i]+=boxx[i-1];boxy[i]+=boxy[i-1];//直接用差分数组还原，压缩空间
	}
	scanf("%d",&m);
	char dir,no;int num=0;
	for(int i=1;i<=m;i++){
		scanf(" %c %c %d",&dir,&no,&num);//这个no只是为了读入方便
		if(dir=='x')printf("%d\n",boxx[num]);
		else printf("%d\n",boxy[num]);
	}
}

ps：建议全程用scanf……别问为什么

（做了一点小改动）