这题是 51Nod 从 Codeforces 上蒯的，原题编号是 CF542A Place Your Ad Here

Description

给定 $n$ 个区间（第一类区间）和另外 $m$ 个区间（第二类区间）（这 $m$ 个区间每个单位长度有一个权值 $c_i$），现在要在 $n$ 个区间和 $m$ 个区间中各选一个区间，使得选出来的第一个区间和选出来的第二个区间的交乘以第二个区间的 $c_i$ 最大。

注意，假如选出来的第一个区间是 $[l, r]$，第二个区间是 $[x, y]$ 且 $[l,r] \cap [x,y] \neq \emptyset$，若交的部分为 $[a, b]$ ，则这一段的贡献为 $(b-a) \times c_i$

Sol

首先可以想到对第一类区间按照左端点为第一关键字升序排序，若第一关键字相等则按照以右端点为第二关键字降序排序。

加入一个区间被另一个区间完全包含，则该区间显然可以略过。

对于每一个第一类区间 $[l_i, r_i]$ ，我们可以通过两次二分查出：1. 左端点 $\geq l_i$ 的区间 2. 右端点 $\leq r_i$ 的区间。从这两类区间中分别二分出在边界的那个第二类区间，与答案取 $\max$

但是注意到，存在一种情况，当前这个区间可能完全被某一个第二类区间包含，这个时候我们只需要把所有的第一类区间插入进一棵线段树，只需要找出左右端点在范围内的最大区间长度即可。

注意 Codeforces 要输出第一类和第二类区间的编号，线段树要记录取最长的区间的编号。稍微注意一下即可。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 3e5 + 5;

int n, m, N;

struct node {
    int l, r, c;
    bool operator < (const node &a) const {
        return l == a.l ? r > a.r : l < a.l;
    }
    LL operator & (const node &a) const {
        if (l <= a.l && r >= a.r) return a.r - a.l;
        if (l >= a.l && r <= a.r) return r - l;
        return std::max(0, std::min(r, a.r) - std::max(l, a.l));
    }
} a[SIZE], b[SIZE], c[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

namespace segmentTree {
    LL len[SIZE << 2];
    #define lson(p) (p << 1)
    #define rson(p) (p << 1 | 1)
    #define pushUp(p) (len[p] = std::max(len[lson(p)], len[rson(p)]))

    void build(int p, int l, int r) {
        if (l == r) return len[p] = 1ll * (a[l].r - a[l].l), void();
        int mid = (l + r) / 2;
        build(lson(p), l, mid), build(rson(p), mid + 1, r);
        pushUp(p);
    }
    LL query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return len[p];
        int mid = (l + r) >> 1; LL ans = 0;
        if (ql <= mid) ans = std::max(ans, query(lson(p), l, mid, ql, qr));
        if (qr > mid) ans = std::max(ans, query(rson(p), mid + 1, r, ql, qr));
        return ans;
    }
} using segmentTree::build; using segmentTree::query;

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) c[i].l = read(), c[i].r = read();
    for (int i = 1; i <= m; ++ i) b[i].l = read(), b[i].r = read(), b[i].c = read();
    std::sort(c + 1, c + n + 1);
    for (int i = 1; i <= n; ++ i) a[i] = c[i];
    N = 1;
    for (int i = 2; i <= n; ++ i) {
        if (a[i].r > a[N].r) a[++ N] = a[i];
    }
    build(1, 1, N); LL ans = -1e18;
    for (int i = 1; i <= m; ++ i) {
        int l = 1, r = N, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (l == mid) break;
            if (a[mid].l < b[i].l) l = mid;
            else r = mid;
        }
        ans = std::max(ans, 1ll * (b[i] & a[l]) * b[i].c);
        int L = l + 1, R; l = 1, r = N, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (a[mid].r > b[i].r) r = mid;
            else l = mid + 1;
        }
        R = r - 1, ans = std::max(ans, 1ll * (b[i] & a[r]) * b[i].c);
        if (R >= L) ans = std::max(ans, 1ll * query(1, 1, N, L, R) * b[i].c);
    }
    printf("%lld\n", ans);
    return 0;
}