难度：省选/NOI-

题目描述

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

输入格式

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

输出格式

        输出仅为一行，包含一个整数，表示 $D_1 + D_2 + \cdots + D_N$的最小值。

说明

        $1≤N≤100000, 1\leq K\leq 2$

题解

        这题教育我们要根据数据范围想思路。一开始毫无思路，结果发现这个K才1~2。
        对于那些不用过河的人，直接预处理掉。对于那些需要过河的人，它们如果需要走位于$a$位置的桥，则需要走的距离是两点（起点、终点）到$a$的距离和再加一，问题转化为在数轴上选一点，使得所有点到该点的距离和最小。这个点显然是中点（中位数）。对于K=1的情况，sort一遍就完了。
        K=2的情况就麻烦得多（K若更大，则更麻烦）。首先每一个人肯定走离自己最近的桥，现在有两个桥，如何确定那些人该走哪一个？可以确定的一点是，如果将所有人按照自己的起点和终点坐标之和做一次排序，那么这两类人（走两个不同的桥）肯定是左边一片，右边一片。这样我们可以枚举这个分割线，然后两侧就转化为K=1的情况。现在问题就转化为如何动态地求一些数的中位数以及这些数到它的距离之和。
        这显然可以用平衡树搞。开两棵平衡树，按坐标点权值排序。$O(logn)$二分出中位数，然后$O(logn)$求距离和。总体时间复杂度$O(nlogn)$。
        在这里为了省空间，可以在右移分割线时将右侧平衡树上的结点“割”下相应的一块给左平衡树，但是我这样做疯狂TLE。后来发现这样做使得左平衡树的平衡性被打破，使得其树高很快达到1000+，原因我也不清楚。解决方法是在移动结点时重新对需要移动的结点进行重随机化处理，以保证树的随机平衡性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>

#define inf (1ll<<50)
using namespace std;
typedef long long ll;

struct Q {
    int l, r;

    bool operator<(Q q) {
        return l + r < q.l + q.r;
    }
};

struct Node {
    int l, r, num, k;
    ll sum, v;
} nd[100100 << 1];
vector<Q> vvp;
vector<int> vvp2;
int k, n, root1, root2;
ll ans;

inline int newNode(ll x) {
    static int p = 1;
    nd[p].v = x, nd[p].num = 1, nd[p].sum = x, nd[p].k = rand();
    return p++;
}

inline void update(int x) {
    nd[x].num = nd[nd[x].l].num + nd[nd[x].r].num + 1;
    nd[x].sum = nd[nd[x].l].sum + nd[nd[x].r].sum + nd[x].v;
}

void split(int rt, int &a, int &b, int s) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (nd[nd[rt].l].num + 1 <= s)a = rt, split(nd[rt].r, nd[a].r, b, s - nd[nd[rt].l].num - 1);
    else b = rt, split(nd[rt].l, a, nd[b].l, s);
    update(rt);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (nd[a].k < nd[b].k)rt = b, merge(nd[rt].l, a, nd[b].l);
    else rt = a, merge(nd[rt].r, nd[a].r, b);
    update(rt);
}

int fd(int rt, int s) {
    if (rt == 0)return 0;
    else if (nd[rt].v == s)return nd[nd[rt].l].num + 1;
    else if (nd[rt].v < s)return nd[nd[rt].l].num + 1 + fd(nd[rt].r, s);
    return fd(nd[rt].l, s);
}

int fdRk(int rt, int s) {
    if (rt == 0)return 0;
    else if (nd[nd[rt].l].num + 1 == s)return rt;
    else if (nd[nd[rt].l].num + 1 < s)return fdRk(nd[rt].r, s - nd[nd[rt].l].num - 1);
    return fdRk(nd[rt].l, s);
}

void trans(int x) {//两棵树交换结点：将右树权值为x的结点转移到左树上
    register int s = fd(root2, x), a, b, c;
    split(root2, a, c, s), split(a, a, b, s - 1), merge(root2, a, c), nd[b].k = rand();//注意这里的重随机化
    s = fd(root1, x), split(root1, a, c, s), merge(a, a, b), merge(root1, a, c);
}

ll getAbs(int rt, ll x) {
    if (rt == 0)return 0;
    if (nd[rt].v < x)return 1ll * (nd[nd[rt].l].num + 1) * x - (nd[nd[rt].l].sum + nd[rt].v) + getAbs(nd[rt].r, x);
    return (nd[nd[rt].r].sum + nd[rt].v) - 1ll * (nd[nd[rt].r].num + 1) * x + getAbs(nd[rt].l, x);
}

inline ll getMid(int rt) {
    if (rt == 0)return 0;
    return nd[fdRk(rt, nd[rt].num >> 1)].v;
}

int main() {
    srand(time(0)), scanf("%d%d", &k, &n);
    for (int i = 1; i <= n; i++) {
        char a, b;
        Q q;
        scanf(" %c", &a), scanf("%d", &q.l), scanf(" %c", &b), scanf("%d", &q.r);
        if (q.l > q.r)swap(q.l, q.r);
        if (a == b)ans += q.r - q.l;
        else vvp.push_back(q);
    }
    if (k == 1) {
        if (vvp.empty()) {//注意判空，否则RE
            cout << ans;
            return 0;
        }
        for (Q q:vvp)vvp2.push_back(q.l), vvp2.push_back(q.r), ++ans;
        sort(vvp2.begin(), vvp2.end());
        register int mid = vvp2[vvp2.size() >> 1];
        for (int s:vvp2)ans += abs(s - mid);
        printf("%lld", ans);
    } else {
        if (vvp.empty()) {
            cout << ans;
            return 0;
        }
        ans += vvp.size();
        ll tmp = inf;
        for (auto &i : vvp) vvp2.push_back(i.l), vvp2.push_back(i.r);
        sort(vvp2.begin(), vvp2.end()), sort(vvp.begin(), vvp.end());
        for (auto &i:vvp2)merge(root2, root2, newNode(i));
        tmp = min(tmp, getAbs(root2, getMid(root2)));
        for (register int i = 0; i < vvp.size() - 1; i++) {
            trans(vvp[i].l), trans(vvp[i].r);
            tmp = min(tmp, getAbs(root1, getMid(root1)) + getAbs(root2, getMid(root2)));
        }
        cout << ans + tmp;
    }
    return 0;
}