？！？！？！考大合综合大考！？！？！？

题意

给定坐标系内 $n$ 个点和 $m$ 个矩形。对任意两点若 $x$ 或 $y$ 坐标相同且连线不碰到任何一个矩形，则连一条边，长度为两点距离。

现有 $q$ 次询问 $b,h$，若要求保留边使连通块个数不超过 $h$，每个连通块产生 $b$ 代价，求代价 $+$ 边权和的最小值。

$n,m\le 2\times10^5$，$q\le 5\times 10^5$，所有值不超过 $10^9$。

思路 Part 1

注意到我们不会跨过一个点去连接两个点，于是一个点只可能向上下左右四个方向连最近的。

以连上下的边为例，我们从左到右扫描线：

• 新遇到一个矩形就在对应 $y$ 的区间 $+1$；

• 然后对于同一列的所有相邻点对，判断组成的区间里的最大值是否为 $0$。是就可以连边。

• 最后没掉一个矩形就在对应区间位置上 $-1$。

直接上线段树维护即可。

总边数是 $O(n)$ 的。记得离散化。

思路 Part 2

找完边了然后呢？

我们发现可以对于每一个 $k$，求出其所需要的最小边权和。

这个怎么求呢？我们联想到 Kruskal 找最小生成树的方法。将边权从小到大依次考虑，若两点不连通就连上，每连一次边就少一个连通块。正确性和 Kruskal 的正确性等价。

由于有一些点是与世隔绝的，所以加完所有边整个图也不一定联通。记连通块个数为 $cnt$，求出的答案为 $sum_k$。

思路 Part 3

询问怎么做？

假设所有询问都没有「至多 $h$ 个连通块」的限制，则答案为 $\min\limits_{i=cnt}^n\{b\times i+sum_i\}$。

这东西不是斜率优化吗？将 $i$ 转化为平面上点 $(i,sum_i)$（要注意这里的平面不是原来的平面）维护下凸包，对于询问二分找到斜率第一个 $\ge -b$ 的位置即可。

加上 $h$ 的限制也没有难多少。按照 $h$ 排序依次加入点 $i$，由于横坐标 $i$ 是按照加入顺序从小到大排序的，所以可以直接用一个栈来维护下凸包。要记得特判掉一些 $h<cnt$ 的情况。

思路 Part 3.5

还没完你先别急。

你写完了闲着没事开始观察凸包。

？诶你这个凸包怎么是原序列啊？

想了想你发现：$i,i+1$ 两点的斜率相当于 $-(sum_{i+1}-sum_i)$；这玩意不是负的一条边权吗？边权不是从大到小排的吗？然后你就发现斜率怎么始终是递增的。

然后你就可以把求凸包的部分删掉换成原序列了。

三个部分的时间复杂度都是 $O(n\log n)$。开 $5$ 秒是怕你常数爆炸。

一些可能爆炸的点：

• 离散化空间要 $3$ 倍，线段树空间要 $12$ 倍，总边数要 $4$ 倍，询问个数是 $5\times 10^5$ 不是 $2\times 10^5$。我试过了是真的。

• 线段树挂点在于不要对叶子 pushdown（不然会 RE），不要少 pushdown。我试过了是真的。

• 建边挂点在于 $x$、$y$ 要分别离散化，两者值域是不同的。我试过了是真的。

• Kruskal 挂点在于跑之前要对边排序。机房里两个人试过了是真的。

• 凸包挂点在于符号方向要搞清楚，建议自己手推一遍。我试过了是真的。

代码

码力赛？赛尼玛。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, q, bx[600002], by[600002], Vx, Vy, idx, fa[200002], sd[200002], cnt, len, ans[500002];
vector<ll> qp[600002], add[600002], del[600002];
struct node1 { ll x, y; } p[200002], st[200002];
struct node2 { ll lx, ly, rx, ry; } mt[200002];
struct node3 { ll x, y, z; } e[800002];
vector<node1> query[600002];
ll fd(ll x) { return fa[x] == x ? x : fa[x] = fd(fa[x]); }
struct sgt {
	ll tr[2400002], tg[2400002];
	void pd(ll x, ll l, ll r) {
		if (! tg[x]) return ;
		ll mid = l + r >> 1, ls = x << 1, rs = x << 1 | 1;
		tg[ls] += tg[x], tg[rs] += tg[x];
		tr[ls] += tg[x], tr[rs] += tg[x];
		tg[x] = 0;
	}        
	void update(ll x, ll l, ll r, ll ansl, ll ansr, ll v) {
		if (ansl <= l && ansr >= r) return tr[x] += v, tg[x] += v, void();
		ll mid = l + r >> 1, ls = x << 1, rs = x << 1 | 1;
		pd(x, l, r);
		if (mid >= ansl) update(ls, l, mid, ansl, ansr, v);
		if (mid <  ansr) update(rs,mid+1,r, ansl, ansr, v);
		tr[x] = max(tr[ls], tr[rs]);
	}
	ll query(ll x, ll l, ll r, ll ansl, ll ansr) {
		if (ansl <= l && ansr >= r) return tr[x];
		if (l == r) return 0;
		ll mid = l + r >> 1, ls = x << 1, rs = x << 1 | 1, res = 0;
		pd(x, l, r);
		if (mid >= ansl) res = max(res, query(ls, l, mid, ansl, ansr));
		if (mid <  ansr) res = max(res, query(rs,mid+1,r, ansl, ansr));
		return res;
	}
	void clear() { memset(tr, 0, sizeof tr); memset(tg, 0, sizeof tg); }
} tr;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (ll i = 1; i <= n; i ++ ) cin >> p[i].x >> p[i].y, bx[++ Vx] = p[i].x, by[++ Vy] = p[i].y;
	for (ll i = 1; i <= m; i ++ ) cin >> mt[i].lx >> mt[i].ly >> mt[i].rx >> mt[i].ry, 
		bx[++ Vx] = mt[i].lx, by[++ Vy] = mt[i].ly, 
		bx[++ Vx] = mt[i].rx, by[++ Vy] = mt[i].ry;
		
	// Part 0. 离散化 
	
	sort(bx + 1, bx + Vx + 1); Vx = unique(bx + 1, bx + Vx + 1) - bx - 1;
	sort(by + 1, by + Vy + 1); Vy = unique(by + 1, by + Vy + 1) - by - 1;
	for (ll i = 1; i <= n; i ++ ) 
		p[i].x = lower_bound(bx + 1, bx + Vx + 1, p[i].x) - bx, 
		p[i].y = lower_bound(by + 1, by + Vy + 1, p[i].y) - by;
	for (ll i = 1; i <= m; i ++ ) 
		mt[i].lx = lower_bound(bx + 1, bx + Vx + 1, mt[i].lx) - bx, 
		mt[i].ly = lower_bound(by + 1, by + Vy + 1, mt[i].ly) - by, 
		mt[i].rx = lower_bound(bx + 1, bx + Vx + 1, mt[i].rx) - bx, 
		mt[i].ry = lower_bound(by + 1, by + Vy + 1, mt[i].ry) - by;
		
	// Part 1. 找到所有极大连通块（只向相邻连边）
	
	// 横边 
	
	for (ll i = 1; i <= n; i ++ ) qp[p[i].y].push_back(i);
	for (ll i = 1; i <= m; i ++ ) add[mt[i].ly].push_back(i), del[mt[i].ry].push_back(i);
	for (ll i = 1, lst; i <= Vy; i ++ ) {
		lst = 0;
		for (ll t : add[i]) tr.update(1, 1, Vx, mt[t].lx, mt[t].rx, 1);
		sort(qp[i].begin(), qp[i].end(), [](ll x, ll y) { return p[x].x < p[y].x; });
		for (ll t : qp[i]) {
			if (!lst) { lst = t; continue; }
			if (!tr.query(1, 1, Vx, p[lst].x, p[t].x)) e[++ idx] = {lst, t, bx[p[t].x] - bx[p[lst].x]};
			lst = t;
		}
		for (ll t : del[i]) tr.update(1, 1, Vx, mt[t].lx, mt[t].rx, -1);
		add[i].clear(), qp[i].clear(), del[i].clear();
	}
	tr.clear(); 
	
	// 竖边 
	
	for (ll i = 1; i <= n; i ++ ) qp[p[i].x].push_back(i);
	for (ll i = 1; i <= m; i ++ ) add[mt[i].lx].push_back(i), del[mt[i].rx].push_back(i);
	for (ll i = 1, lst; i <= Vx; i ++ ) {
		lst = 0;
		for (ll t : add[i]) tr.update(1, 1, Vy, mt[t].ly, mt[t].ry, 1);
		sort(qp[i].begin(), qp[i].end(), [](ll x, ll y) { return p[x].y < p[y].y; });
		for (ll t : qp[i]) {
			if (!lst) { lst = t; continue; }
			if (!tr.query(1, 1, Vy, p[lst].y, p[t].y)) e[++ idx] = {lst, t, by[p[t].y] - by[p[lst].y]};
			lst = t;
		}
		for (ll t : del[i]) tr.update(1, 1, Vy, mt[t].ly, mt[t].ry, -1);
		add[i].clear(), qp[i].clear(), del[i].clear();
	}
	tr.clear(); 
	
//	Part 2. 计算钦定机场个数后道路最小总长。
	
	for (ll i = 1; i <= n; i ++ ) fa[i] = i;
	sort(e + 1, e + idx + 1, [](node3 x, node3 y) { return x.z < y.z; });
	cnt = n;
	for (ll i = 1, x, y, z, fx, fy; i <= idx; i ++ ) {
		x = e[i].x, y = e[i].y, z = e[i].z;
		fx = fd(x), fy = fd(y);
		if (fx == fy) continue;
		cnt --; fa[fx] = fy; sd[cnt] = sd[cnt + 1] + z;
	}
	
//	Part 3. 对于每个询问形如计算 (k * x + sd) min。怎么是原序列啊。 

	for (ll b, h, i = 1; i <= q; i ++ ) {
		cin >> b >> h;
		if (h < cnt) cout << "-1\n";
		else {
			ll l = cnt, r = h - 1, res = h;
			while (l <= r) {
				ll mid = l + r >> 1;
				if (sd[mid] - sd[mid + 1] < b) res = mid, r = mid - 1;
				else l = mid + 1;
			}
			cout << res * b + sd[res] << "\n";
		}
	}
}