自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:20:00，当前版本为作者最后更新于2020-08-11 16:46:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

kcm的原题。。

貌似是个组合数（？

此处食用效果更佳哦

$\sf Solution$

对于每一个点，我们需要统计与它同一行的点数 $a$ 和同一列的点数 $b$ ，则该点对结果 $ans$ 的贡献为 $(a-1)\times (b-1)$ 。

当然如果统计两重循环的话，那肯定是会TLE的啦。那么就要加一个预处理了：

用两个 map 数组分别统计 $a$ 和 $b$ 。

之所以考虑用 map 是因为开数组可能会炸，后来发现好像不会……

$\sf P.S.$

因为有乘运算，并且 $n\leq 10^5$ ，所以不开 long long是要炸掉的哦。

$\sf Code$

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
struct node
{
	int x,y;
}a[100004];
int n;
long long ans;
map<long long,long long>m1,m2;//long long!
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&a[i].x,&a[i].y);//读入
	for(int i=1;i<=n;++i)
		++m1[a[i].x],++m2[a[i].y];//分别统计行和列
	for(int i=1;i<=n;++i)
		ans+=(m1[a[i].x]-1)*(m2[a[i].y]-1);//根据那啥算
	printf("%lld",ans);
	return 0;
}