题目

传送门：有账号才行。

题目描述 幻想乡有 $N$ 个区域，从 $1$ 到 $N$ 编号，神奈子希望通过修建“御神渡”来让所有的区域互相可达，“御神渡”可以看做两个区域之间的一个双向道路。在 $i$ 区域与 $j$ 区域之间修建“御神渡”，需要在 $i$ 区域耗费 $C_i$ 的神力新建神社，在 $j$ 区域耗费 $C_j$ 的神力新建神社，然后将两个神社配对。如果一个区域和其他多个区域建立“御神渡”，那么在这个区域要为每个“御神渡”建一个神社，即多个“御神渡”不能共用神社。

“御神渡”会促进两个区域的人口流动，而人口的流动就会带来文化的交流、信仰的增多。如果 $i$ 区域的人口为 $A_i$ 而 $j$ 区域有的人口为 $A_j$ ，则神奈子将会得到 $A_i\times A_j$ 的神力。

神奈子希望修建尽量少的“御神渡”，使得 $N$ 个区域互相可达。在这个前提下，神奈子还希望自己总神力的减少量最小（注意该值可能为负，即神奈子的神力不减反增）。

输入格式 第一行一个非负整数 $N$ ，表示区域的数量。

第二行 $N$ 个非负整数 $A_i$ ，分别表示 $N$ 个区域的人口。数据保证每个区域的人口互不相等。

第三行 $N$ 个非负整数 $C_i$ ，分别表示在 $N$ 个区域建神社要花费的神力。

输出格式 输出一个整数，表示神奈子总神力的减少量的最小值。

数据范围与约定 对于所有数据，$N\le 10^5,A_i\le 2\times 10^6,C_i\le 10^9$ 。

思路

很明显，将 $(u,v)$ 的边权视作 $C_u+C_v-A_u\times A_v$（即在 $u$ 和 $v$ 之间建立“御神渡”的净花费），则原题等价于求这张图里的最小生成树。

耿直的暴力

暴力求最小生成树，$\mathcal{O}(n^2)$ 。因为是完全图。

斜率优化

思考为什么这道题可以有比最小生成树更快的算法？必然是因为 边权的特殊性。

不难证明，所有与 $u$ 相连的边中最小的一条一定是生成树中的边。（可以用 $\mathtt{p}\mathtt{r}\mathtt{i}\mathtt{m}$ 或 $\mathtt{k}\mathtt{r}\mathtt{u}\mathtt{s}\mathtt{k}\mathtt{a}\mathtt{l}$ 的过程证明，或模仿二者的反证法来证明）。怎么找最小的一条边？

考虑 斜率优化。推一推斜率优化的式子，发现是 $C_u-C_v<A_x(A_u-A_v)$ 时 $u$ 更优（考虑边 $⟨x,u⟩$ 和 $⟨x,v⟩$ 谁边权更小）。那么假定 $A_v<A_u$ ，第 $x$ 个点定义为 $(C_x,A_x)$ ，上式等价于 $K_{uv}<A_x$ 。不难发现，维护的形状是下凸包。

先求凸包，按照 $A$ 值排序后跑，$\mathcal{O}(n\log n)$ 。然而现实很残酷——只有 $60\mathtt{p}\mathtt{t}\mathtt{s}$ ！

改进版

为什么不是 $100$ 分到手？因为有可能 试图连接自环！

也就是说，斜率优化求决策点的时候，最佳决策点是自己 我也很绝望啊。

那么我们迫切的需要一个新方法：考虑每一个点的时候，只把其他的拿出来做凸包。回到了$\mathcal{O}(n^2)$ ……

等等！好像对于 $[1,mid]$ 中的每一个 $x$ ，$(mid,r]$ 中的任意一个点都可以当做决策点。这提示我们 分治！

用 $work(l,r)$ 表示处理 $[l,r]$ 内部的互相贡献，首先递归，其次 交叉计算贡献。

这很像 $\mathtt{c}\mathtt{d}\mathtt{q}$分治，能做到 $\mathcal{O}(n\log n)$ 。应该有 $80$ 分了吧？

正解

为什么还不过，去™的垃圾题

因为 连接一次不够……有可能只连接了 $\frac{n}{2}$ 条边（两个点 选择了同一条边……）

好吧，把点染色，一个联通块中的点染一种颜色，问题转化为 某一颜色向异色点中连边。

我们把颜色拿来排个序，一样可以分治……个屁！为什么不能分治了？因为交叉计算贡献的时候，得依靠 $A$ 值有序才行！

这个问题好像有点熟悉……有两个维度 $(x,y)$，要求 $x$ 和 $y$ 都有序。二维偏序？

做过二维偏序板题吗？做过的都明白用的方法是 $\mathtt{c}\mathtt{d}\mathtt{q}$分治！

现在这个题，好像有点板？（大雾）

$CDQ$ 分治，先对颜色排序，再归并 $A$ 值，$\mathcal{O}(n{\log }^{2}n)$ 。

关于复杂度：当前有 $m$ 种颜色，则至少连接 $\frac{m}{2}$ 条边，也就是颜色减少一半。开始有 $n$ 种颜色，最多做 $\log n$ 次生成树。生成树复杂度与上解法三同，$\mathcal{O}(n\log n)$ 。实际上，很少有数据能够卡到做 $\log n$ 次生成树（大多数做个 $2$ 到 $5$ 次就搞定了），运行起来海星。

代码

#include <cstdio> #include <iostream> #include <algorithm> #include <vector> using namespace std; struct Point{ // 向量（或者点） int x, y; Point(int X=0,int Y=0):x(X),y(Y){ } Point operator+(const Point &that)const{ return Point(x+that.x,y+that.y); } Point operator-(const Point &that)const{ return Point(x-that.x,y-that.y); } friend long long operator*(const Point &a,const Point &b){ return 1ll*a.x*b.y-1ll*a.y*b.x; } friend Point operator*(const int &u,const Point &v){ return Point(u*v.x,u*v.y); } }; const int MaxN = 100000; int allColor, n, fa[MaxN]; inline int findColor(int a){ if(fa[a] != a) // 并查集判断颜色相同否 fa[a] = findColor(fa[a]); return fa[a]; } struct Node{ Point p; int color; bool operator < (const Node &that)const{ if(color != that.color) return color < that.color; return this->lessThan(that); } bool lessThan(const Node &that)const{ return p.x < that.p.x; } } node[MaxN]; long long edgeValue(int i,int j){ // 暴力计算边的权值 return -1ll*node[i].p.x*node[j].p.x+node[i].p.y+node[j].p.y; } int ys[MaxN]; // 将颜色离散化 int* convexHull(int l,int r,int *result){ int *top = result; for(int i=l; i<r; ++i){ while(top-result >= 2) if((node[i].p-node[*(top-1)].p)*(node[*(top-1)].p-node[*(top-2)].p) >= 0) -- top; // 维护下凸包 else break; *(top ++) = i; } return top; } int temp[MaxN]; pair<long long,int> choice[MaxN]; Node temp2[MaxN]; // to sort it void dealWith(int L,int R,int l,int r){ // [L,R] for color. [l,r) for index. if(L == R) return ; int MID = (L+R)>>1, mid; for(mid=l; mid<r; ++mid) if(ys[node[mid].color] > MID) break; dealWith(L,MID,l,mid); // left part dealWith(MID+1,R,mid,r); // right part Point xl; // K for(int i=mid, *now=temp, *tail=convexHull(l,mid,temp); i<r; ++i){ xl = Point(1,node[i].p.x); while(tail-now >= 2) if((node[*(now+1)].p-node[*now].p)*xl >= 0) ++ now; else break; // choice: first是边权, second是与谁相连 if(choice[node[i].color].second == -1 or edgeValue(i,*now) < choice[node[i].color].first) choice[node[i].color] = make_pair(edgeValue(i,*now),node[*now].color); } for(int i=l, *now=temp, *tail=convexHull(mid,r,temp); i<mid; ++i){ xl = Point(1,node[i].p.x); while(tail-now >= 2) if((node[*(now+1)].p-node[*now].p)*xl >= 0) ++ now; else break; if(choice[node[i].color].second == -1 or edgeValue(i,*now)<choice[node[i].color].first) choice[node[i].color] = make_pair(edgeValue(i,*now),node[*now].color); } for(int i=l, j=mid, k=l; i<mid or j<r; ) if(j == r or (i < mid and node[i].lessThan(node[j]))) temp2[k ++] = node[i ++]; else // 将其排序 temp2[k ++] = node[j ++]; for(int i=l; i<r; ++i) node[i] = temp2[i]; } long long ans = 0; bool setMST(){ for(int i=0; i<n; ++i){ fa[i] = i; ys[i] = 0; choice[i].second = -1; } sort(node,node+n); allColor = 0; for(int i=0; i<n; ){ ys[node[i].color] = ++allColor; for(; i<n and ys[node[i].color] == allColor; ++i); } if(allColor == 1) return true; // finished! dealWith(1,allColor,0,n); for(int i=0; i<n; ++i){ if(not ys[node[i].color]) continue; ys[node[i].color] = 0; if(choice[choice[node[i].color].second].second == node[i].color and node[i].color > choice[node[i].color].second) continue; // they two choose the same edge fa[node[i].color] = choice[node[i].color].second; ans += choice[node[i].color].first; } for(int i=0; i<n; ++i) node[i].color = findColor(node[i].color); return false; } int main(){ scanf("%d",&n); for(int i=0; i<n; ++i){ node[i].color = i; scanf("%d",&node[i].p.x); } for(int i=0; i<n; ++i) scanf("%d",&node[i].p.y); while(not setMST()); cout << ans; return 0; }