【题解】USACO 2020Feb Silver Triangles

思路分析

很简单但是（至少对于lyc来说）细节比较多。

首先离散化是必须的。然后先考虑暴力。把某一行/列中的点记在一个vector里。枚举每一个点作为三角形的直角顶点，暴力找有哪些点可以与它构成三角形。显然是$\mathcal{O(n^2)}$的。 （考场上居然算错复杂度了草

然后我们考虑优化查找“与当前枚举的点可以构成三角形的点对”的过程。

为了方便，我们用$(x_i,y_i)$表示第$i$个点的坐标。

我们仍然枚举在三角形中作为直角顶点的点$d$，用$(x_d,y_d)$代表。显然，与当前顶点组成三角形的点对要满足的条件是“点对中一个点与$(x_d,y_d)$的横坐标相同，另一个点与$(x_d,y_d)$纵坐标相同”，说人话就是也就是当前点所处的行上选一个，所在列选一个。我们设当前列有$k1$个点，第$i$个点的编号是$a_i$；当前行有$k2$个点，第$i$个点的编号是$b_i$。

那么这些点对为

$(a_1,b_1),(a_1,b_2)\dots(a_1,b_{k2}),(a_2,b_1),(a_2,b_2)\dots (a_{k1},b_{k2})$

我们的答案为$\sum\limits_{i=1}^{k1} \sum\limits_{j=1}^{k2} \left|y_d-y_{a_i} \right| \times \left|x_d-x_{b_j} \right|$

考虑前缀和优化，具体来说就是每一行/列对于点的原始坐标排序，然后做前缀和。

然后我们可以通过前缀和在$\mathcal{O(1)}$时间内求出这个式子的值，会在代码说明里具体说明。

然后累加答案就可以了。

已经懂了的就不用看下去了wwww

代码说明

先放代码：

有点乱 将就着看吧wwwwww

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
#define int long long
const int MAXN=100005;
const int MOD=1e9+7;
int n;
int mx,my;
pair<int,int> a[MAXN];
int ls1[MAXN],ls2[MAXN];
int x[MAXN],y[MAXN];
vector<int> vx[MAXN],vy[MAXN];
vector<int> sumx[MAXN],sumy[MAXN];
int ans=0;

signed main()

{
    //读入
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
		ls1[i]=a[i].first;
		ls2[i]=a[i].second;
	}

	//离散化
	sort(ls1+1,ls1+1+n);
	sort(ls2+1,ls2+1+n);
	mx=unique(ls1+1,ls1+1+n)-ls1-1;
	my=unique(ls2+1,ls2+1+n)-ls2-1;
	for (int i=1;i<=n;i++)
		x[i]=lower_bound(ls1+1,ls1+1+mx,a[i].first)-ls1;

	for (int i=1;i<=n;i++)
		y[i]=lower_bound(ls2+1,ls2+1+my,a[i].second)-ls2;

	for (int i=1;i<=n;i++){
		vx[x[i]].push_back(y[i]);
		vy[y[i]].push_back(x[i]);
        //注意这里存的是y[i]和x[i]，不是点的编号。
	}

	//处理前缀和 & 排序
	for (int i=1;i<=mx;i++){
		sort(vx[i].begin(),vx[i].end());
		int sum=0;
		sumx[i].push_back(0);
		for (int j=0;j<vx[i].size();j++){
			sum+=ls2[vx[i][j]];
			sumx[i].push_back(sum);
		}
	}

	for (int i=1;i<=my;i++){
		sort(vy[i].begin(),vy[i].end());
		int sum=0;
		sumy[i].push_back(0);
		for (int j=0;j<vy[i].size();j++){
			sum+=ls1[vy[i][j]];
			sumy[i].push_back(sum);
		}
	}

	for (int i=1;i<=n;i++){
		int posx=lower_bound(vx[x[i]].begin(),vx[x[i]].end(),y[i])-vx[x[i]].begin();//点i在x值相同的一列中y值的排名
		int posy=lower_bound(vy[y[i]].begin(),vy[y[i]].end(),x[i])-vy[y[i]].begin();//点i在y值相同的一行中x值的排名
		int sz1=vx[x[i]].size();
		int tmpx=(posx*ls2[y[i]]-sumx[x[i]][posx])%MOD+(sumx[x[i]][sz1]-sumx[x[i]][posx+1]-(sz1-posx-1)*ls2[y[i]])%MOD;

		int sz2=vy[y[i]].size();
		int tmpy=(posy*ls1[x[i]]-sumy[y[i]][posy])%MOD+(sumy[y[i]][sz2]-sumy[y[i]][posy+1]-(sz2-posy-1)*ls1[x[i]])%MOD;
		ans+=tmpx*tmpy;
		ans%=MOD;
	}

	cout<<ans<<endl;
	return 0;
}

离散化不用多讲，x,y分别存放坐标离散化后的横/纵坐标。

处理前缀和也没啥好讲的wwww，要注意的是在最前面push_back一个0以免越界。

然后用lower_bound查找当前点在当前行/列的排名，意义见注释。

sz1,sz2 分别是当前列/行点的个数+1（因为前面多了一个0

我们可以把上面的式子写成 $\sum\limits_{i=1}^{k1} \left|y_d-y_{a_i} \right| \times \sum\limits_{i=1}^{k2}\left|x_d-x_{b_i} \right|$

然后我们可以分别算出这两个式子的值，也就是代码中的tmpx,tmpy。

它们的意义分别是“在当前列的所有点‘与当前点的纵坐标之差’之和”，“在当前行的所有点‘与当前点的横坐标之差’之和”。

可以用前缀和求出，对于位置小于和大于（当然是在当前行/列中）当前点的点分别处理。

乘一下，累加答案，模一下。

做完了

最后说句闲话（？） 抓到bug的话请务必告诉我wwww

毕竟没写过两篇题解（