题目地址：洛谷：【P3644】[APIO2015]八邻旁之桥 – 洛谷、BZOJ：Problem 4071. — [Apio2015]巴邻旁之桥

题目描述

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 A 和区域 B。
每一块区域沿着河岸都建了恰好 1000000001 栋的建筑，每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离，河的宽度也是 1 个单位长度。区域 A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。
城市中有 N 个居民。第 i 个居民的房子在区域 Pi 的 Si 号建筑上，同时他的办公室坐落在 Qi 区域的 Ti 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 K 座横跨河流的大桥。
由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。
当政府建造最多 K 座桥之后，设 Di 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 D1+D2+⋯+DN 最小。

输入输出格式

输入格式：
输入的第一行包含两个正整数 K 和 N，分别表示桥的上限数量和居民的数量。
接下来 N 行，每一行包含四个参数：Pi,Si,Qi 和 Ti，表示第 i 个居民的房子在区域 Pi 的 Si 号建筑上，且他的办公室位于 Qi 区域的 Ti 号建筑上。

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

输入输出样例

输入样例#1：

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

输出样例#1：

24

输入样例#2：

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

输出样例#2：

22

说明

所有数据都保证：Pi 和 Qi 为字符 “A” 和 “B” 中的一个， 0≤Si,Ti≤1000000000，同一栋建筑内可能有超过 1 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 1）。
子任务 1 （8 分） K=1 1≤N≤1000
子任务 2 （14 分） K=1 1≤N≤100000
子任务 3 （9 分） K=2 1≤N≤100
子任务 4 （32 分） K=2 1≤N≤1000
子任务 5 （37 分） K=2 1≤N≤100000

题解

由于位置坐标比较大，先离散化这些位置。首先对于同侧的情况，建桥对其无影响，单独统计加入答案即可。
注意到K只有1和2两种取值，分开考虑。
K=1的时候，直接将桥建在所有家和办公室位置的中间（中位数）即可，这个位置的结果一定最优。
K=2的时候，考虑将这些线段分成两部分，以线段中点作为区分，中点较小的一部分走一座桥，另一部分走另一座桥。我们可以枚举排序后[1, i]内的线段属于一部分，其他属于另一部分，分别求中点计算答案。
计算中点可以考虑使用权值线段树来处理。上述算法的复杂度是O(N \log N)。
但是非常可惜，直接做会爆long long，这里用一点小trick可以避免答案过大，详情参见代码。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isAB(char c) {
    return c == 'A' || c == 'B';
}

inline char readAB() {
    char c;
    while(!isAB(c = fgc()));
    return c;
}

const int MAXN = 200005;

std::vector<LL> tmp;

struct SegmentTree {
#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
    LL val[MAXN << 2], sum[MAXN << 2];
    inline void insert(int o, int l, int r, int x) {
        val[o]++; sum[o] += tmp[x];
        if(l == r) return;
        if(x <= mid) insert(lch, l, mid, x);
        else insert(rch, mid + 1, r, x);
    }
    inline void erase(int o, int l, int r, int x) {
        val[o]--; sum[o] -= tmp[x];
        if(l == r) return;
        if(x <= mid) erase(lch, l, mid, x);
        else erase(rch, mid + 1, r, x);
    }
    inline int queryrk(int o, int l, int r, int rk) {
        if(l == r) return l;
        int lsiz = val[lch];
        if(rk <= lsiz) return queryrk(lch, l, mid, rk);
        else return queryrk(rch, mid + 1, r, rk - lsiz);
    }
    inline LL querysum(int o, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr) return sum[o];
        LL res = 0;
        if(ll <= mid) res += querysum(lch, l, mid, ll, rr);
        if(rr > mid) res += querysum(rch, mid + 1, r, ll, rr);
        return res;
    }
    inline LL querysiz(int o, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr) return val[o];
        LL res = 0;
        if(ll <= mid) res += querysiz(lch, l, mid, ll, rr);
        if(rr > mid) res += querysiz(rch, mid + 1, r, ll, rr);
        return res;
    }
} tr1, tr2;

int k, n, N;
LL ans;

struct Node {
    LL s, t;
    inline bool operator<(const Node &rhs) const {
        return s + t < rhs.s + rhs.t;
    }
};

std::vector<Node> info;

inline int main1() {
    LL sum1 = 0, sum2 = 0;
    for(int i = 1; i <= N / 2; i++) {
        sum1 += tmp[i];
    }
    for(int i = N / 2 + 1; i <= N; i++) {
        sum2 += tmp[i];
    }
    printf("%lld", ans + sum2 - sum1);
    return 0;
}

inline int main2() {
    if(!info.size()) {
        printf("%lld", ans); return 0;
    }
    std::sort(info.begin(), info.end());
    for(int i = 0; i < info.size(); i++) {
        info[i].s = std::lower_bound(tmp.begin(), tmp.end(), info[i].s) - tmp.begin();
        info[i].t = std::lower_bound(tmp.begin(), tmp.end(), info[i].t) - tmp.begin();
    }
    for(int i = 0; i < info.size(); i++) {
        tr1.insert(1, 1, N, info[i].s); tr1.insert(1, 1, N, info[i].t);
    }
    LL mn = 1e18;
    for(int i = 0; i < info.size(); i++) {
        tr1.erase(1, 1, N, info[i].s); tr1.erase(1, 1, N, info[i].t);
        tr2.insert(1, 1, N, info[i].s); tr2.insert(1, 1, N, info[i].t);
        LL m1 = tr1.queryrk(1, 1, N, tr1.val[1] / 2), 
            m2 = tr2.queryrk(1, 1, N, tr2.val[1] / 2),
            d1 = tmp[m1] * tr1.querysiz(1, 1, N, 1, m1) - tr1.querysum(1, 1, N, 1, m1) 
                + tr1.querysum(1, 1, N, m1, N) - tmp[m1] * tr1.querysiz(1, 1, N, m1, N),
            d2 = tmp[m2] * tr2.querysiz(1, 1, N, 1, m2) - tr2.querysum(1, 1, N, 1, m2) 
                + tr2.querysum(1, 1, N, m2, N) - tmp[m2] * tr2.querysiz(1, 1, N, m2, N);
        mn = std::min(mn, d1 + d2);
    }
    printf("%lld", ans + mn);
    return 0;
}

LL si, ti;
char pi, qi;

int main() {
    k = readint(); n = readint();
    for(int i = 1; i <= n; i++) {
        pi = readAB(); si = readint(); qi = readAB(); ti = readint();
        if(si > ti) {
            std::swap(pi, qi); std::swap(si, ti);
        }
        if(pi == qi) ans += ti - si;
        else ans++, info.push_back(Node {si, ti});
    }
    tmp.push_back(-1);
    for(int i = 0; i < info.size(); i++) {
        tmp.push_back(info[i].s);
        tmp.push_back(info[i].t);
    }
    std::sort(tmp.begin(), tmp.end());
    N = tmp.size() - 1;
    if(k == 1) return main1();
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    N = tmp.size() - 1;
    return main2();
}