LOJ

分析

对于一张课桌，如果其区间被另外的课桌包含，那么它是没用的，可以去掉。那么剩下的课桌满足左右端点都递增。

对于每个班的学生，将其按身高排序，显然每两个人坐同一张课桌更优，且一定是身高小的坐 $l$ 小的桌子。

那么每对学生选择的桌子满足决策单调性，可以分治处理。在计算代价时，把所有班当前组的 $2m$ 个人拿出来按照身高排序，然后维护一个前缀和，这样子只需要二分一下就可以计算了。

时间复杂度应该是 $\mathcal{O}(k\log n\log m)$ 的。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 200000 + 10;

int m, n, k;
struct desk { int l, r; } q[N];
vector<int> v[N];
int sta[N << 1], top = 0;
ll s[N << 1], ans = 0;

ll calc(desk x) {
    int l = upper_bound(sta + 1, sta + top + 1, x.l) - sta - 1;
    int r = lower_bound(sta + 1, sta + top + 1, x.r) - sta;
    return 1ll * x.l * l - s[l] + s[top] - s[r - 1] - 1ll * x.r * (top - r + 1);
}

void solve(int l, int r, int L, int R) {
    if (l > r || L > R) return;
    int mid = (l + r) >> 1;
    top = 0;
    for (int i = 1; i <= m; ++i)
        sta[++top] = v[i][mid << 1], sta[++top] = v[i][mid << 1 | 1];
    sort(sta + 1, sta + top + 1);
    for (int i = 1; i <= top; ++i) s[i] = s[i - 1] + sta[i];
    ll res = LONG_LONG_MAX; int p;
    for (int i = L; i <= R; ++i) {
        ll now = calc(q[i]);
        if (now < res) res = now, p = i;
    }
    ans += res;
    solve(l, mid - 1, L, p), solve(mid + 1, r, p, R);
}

int main() {
    m = read(), n = read(), k = read();
    for (int i = 1; i <= k; ++i) q[i].l = read(), q[i].r = read();
    sort(q + 1, q + k + 1, [](desk a, desk b) {
        return a.l < b.l || (a.l == b.l && a.r > b.r);
    });
    int c = 0;
    for (int i = 1; i <= k; ++i)
        if (i == 1 || q[i].r > q[c].r) q[++c] = q[i];
    k = c;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n << 1; ++j)
            v[i].emplace_back(read());
        sort(v[i].begin(), v[i].end());
    }
    solve(0, n - 1, 1, k);
    printf("%lld\n", ans);
    return 0;
}