Rockdu's Blog

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 AA 和区域 BB。

每一块区域沿着河岸都建了恰好 10000000011000000001 栋的建筑，每条岸边的建筑都从 00 编号到 10000000001000000000。相邻的每对建筑相隔 11 个单位距离，河的宽度也是 11 个单位长度。区域 AA 中的 ii号建筑物恰好与区域 BB 中的 ii 号建筑物隔河相对。

城市中有 NN 个居民。第 ii 个居民的房子在区域 PiPi 的 SiSi 号建筑上，同时他的办公室坐落在 QiQi 区域的 TiTi 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 KK 座横跨河流的大桥。

由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。

当政府建造最多 KK 座桥之后，设 DiDi 表示第 ii 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 D1+D2+⋯+DND1+D2+⋯+DN 最小。

输入格式

输入的第一行包含两个正整数 KK 和 NN，分别表示桥的上限数量和居民的数量。

接下来 NN 行，每一行包含四个参数：Pi,Si,QiPi,Si,Qi 和 TiTi，表示第 ii 个居民的房子在区域 PiPi 的 SiSi 号建筑上，且他的办公室位于 QiQi 区域的 TiTi 号建筑上。

输出格式

输出仅为一行，包含一个整数，表示 D1+D2+⋯+DND1+D2+⋯+DN 的最小值。

样例一

input

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

output

24

样例二

input

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

output

22

子任务

所有数据都保证：PiPi 和 QiQi 为字符 “A” 和 “B” 中的一个， 0≤Si,Ti≤10000000000≤Si,Ti≤1000000000，同一栋建筑内可能有超过 11 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 11）。

• 子任务 1 （8 分）
  • K=1K=1
  • 1≤N≤10001≤N≤1000
• 子任务 2 （14 分）
  • K=1K=1
  • 1≤N≤1000001≤N≤100000
• 子任务 3 （9 分）
  • K=2K=2
  • 1≤N≤1001≤N≤100
• 子任务 4 （32 分）
  • K=2K=2
  • 1≤N≤10001≤N≤1000
• 子任务 5 （37 分）
  • K=2K=2
  • 1≤N≤1000001≤N≤100000

首先我们想，公司和家在同一边的肯定可以直接到达，加入答案就可以。

然后其实所有的家和公司是等价的，因为算距离的时候都是和桥的位置算绝对值。

现在K=1时，我们就是要选一个点使得它到所有点的距离和最小，那么这个点一定就是所有点坐标的中位数（正确性比较显然，不做证明），我们找出中位数就好了。

那么K=2呢？

注意到一个人选择桥1，不选择桥2的条件，其实是看他家和公司的中间点偏向于哪一边（又一个结论）。考虑公司如果两个桥刚好在公司到家之间，那么选哪个都无所谓。如果一个在公司到家之间，一个不在，那么在之间的一定离中间点近。如果两个都不在家和公司之间，那么我们考虑把家和公司同时向中点移动一个，那么答案是不会改变的！所以中点到桥的距离哪边短，我们就决定选哪个桥。这样的话，我们只要对每一个人家到公司的中点排序，来把所有人分到左右两边的桥上，对于左右两边都维护一个中位数即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#define LL long long
#define N (1e9)
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5;
char a[3], b[3];
int u, v, n, k, cnt; 
LL ans, base, mn = 0x3f3f3f3f3f3f3f3f;
struct Interval {
	int l, r, mid2; Interval() {}
	Interval(int rl, int rr){l = rl, r = rr, mid2 = l + r;}
	bool operator <(const Interval & A) const{return mid2 < A.mid2;}
}itv[maxn << 1];
template<typename T >
T abs(T a) {return a < 0 ? -a : a;}

namespace SGT {
	const int L = 0, R = 1;
	struct node {int sz, ch[2]; LL sum;}tree[maxn * 128];
	int cnt;
	void push_up(int rt) {
		tree[rt].sz = tree[tree[rt].ch[R]].sz + tree[tree[rt].ch[L]].sz;
		tree[rt].sum = tree[tree[rt].ch[R]].sum + tree[tree[rt].ch[L]].sum;
	}
	void ins(int pos, int & rt, int tl = 0, int tr = N) {
		if(!rt) rt = ++cnt;
		if(tl == tr) 
			return ++tree[rt].sz, tree[rt].sum += pos, void();
		int mid = tl + tr >> 1;
		if(pos <= mid) ins(pos, tree[rt].ch[L], tl, mid);
		else ins(pos, tree[rt].ch[R], mid + 1, tr);
		push_up(rt);
	}
	void del(int pos, int & rt, int tl = 0, int tr = N) {
		if(!rt) return ;
		if(tl == tr) 
			return --tree[rt].sz, tree[rt].sum -= pos, void();
		int mid = tl + tr >> 1;
		if(pos <= mid) del(pos, tree[rt].ch[L], tl, mid);
		else del(pos, tree[rt].ch[R], mid + 1, tr);
		push_up(rt);
	}
	int Count(int l, int r, int rt, int tl = 0, int tr = N) {
		if(!rt) return 0;
		if(tl == l && tr == r) return tree[rt].sz;
		int mid = tl + tr >> 1;
		if(r <= mid) return Count(l, r, tree[rt].ch[L], tl, mid);
		else if(l > mid) return Count(l, r, tree[rt].ch[R], mid + 1, tr);
		else return Count(l, mid, tree[rt].ch[L], tl, mid) + Count(mid + 1, r, tree[rt].ch[R], mid + 1, tr);
	}
	int Qnum(int k, int rt, int tl = 0, int tr = N) {
		if(!rt) return 0;
		if(tl == tr) return tl;
		int ls = tree[rt].ch[L], rs = tree[rt].ch[R], mid = tl + tr >> 1;
		if(k <= tree[ls].sz) return Qnum(k, ls, tl, mid);
		else return Qnum(k - tree[ls].sz, rs, mid + 1, tr);
	}
	LL Qsum(int l, int r, int rt, int tl = 0, int tr = N) {
		if(!rt) return 0;
		if(tl == l && tr == r) return tree[rt].sum;
		int mid = tl + tr >> 1;
		if(r <= mid) return Qsum(l, r, tree[rt].ch[L], tl, mid);
		else if(l > mid) return Qsum(l, r, tree[rt].ch[R], mid + 1, tr);
		else return Qsum(l, mid, tree[rt].ch[L], tl, mid) + Qsum(mid + 1, r, tree[rt].ch[R], mid + 1, tr);
	}
}
int A, B, Bsize, Asize, tot, mdn, mdt;

LL Gans(int rt, int size) {
	LL ans = 0;
	if(!size) return 0;
	mdn = SGT::Qnum((size + 1) / 2, rt);
	mdt = SGT::Count(0, mdn, rt);
	ans += 1ll * mdn * mdt - SGT::Qsum(0, mdn, rt);
	ans += SGT::Qsum(mdn + 1, N, rt) - 1ll * mdn * (size - mdt);
	return ans;
}

int main() {
	scanf("%d%d", &k, &n);
	For(i, 1, n) {
		scanf("%s%d%s%d", a, &u, b, &v);
		if(u > v) swap(u, v);
		if(a[0] == b[0]) base += v - u;
		else {
			itv[++cnt] = Interval(u, v);
			SGT::ins(u, B), SGT::ins(v, B), Bsize += 2;
		}
	}
	base += Bsize / 2;
	ans = Gans(B, Bsize);
	if(k == 1) return printf("%lld", ans + base), 0;
	tot = Bsize / 2, mn = ans;
	sort(itv + 1, itv + tot + 1);
	for(register int i = 1; i <= tot; ++i) {
		while(1) {
			SGT::del(itv[i].l, B), SGT::del(itv[i].r, B);
			SGT::ins(itv[i].l, A), SGT::ins(itv[i].r, A);
			Bsize -= 2, Asize += 2;
			if(itv[i].mid2 != itv[i + 1].mid2) break;
			else ++i;
		}
		ans = 0;
		ans += Gans(A, Asize);
		ans += Gans(B, Bsize);
		mn = min(mn, ans);
	}
	printf("%lld", mn + base);
	return 0;
} 

我