51nod 1480 打广告

博主： tony102
发布时间：2021 年 09 月 20 日
970 次浏览
暂无评论
1126字数
分类：题解

这题是 51Nod 从 Codeforces 上蒯的，原题编号是 [CF542A Place Your Ad Here](https://www.luogu.com.cn/problem/CF542A)

## 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

```cpp
#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;
}
```

最后修改：2021 年 09 月 24 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

看透一切的人士
催更名人传
看透一切的人士
催更
tham
催更！！！！
wyzwyz
建议把从“小有名气的贫僧”之后的全删了，包括我这句，前面都是一...
潜心学习的打工人
催更

CF82D Two out of Three
评论数： 0
基本微积分定理
评论数： 0
写在 CSP-S2021 前
评论数： 6
20211108 数数 (count)
评论数： 0
20211110 漂亮大厨 (cook)
评论数： 0

51nod 1480 打广告

tony102 • 2021 年 09 月 20 日

这题是 51Nod 从 Codeforces 上蒯的，原题编号是 [CF542A Place Your Ad Here](https://www.luogu.com.cn/problem/CF542A)

## Description

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

## Sol

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

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

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

## Code

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

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

int n, m, N;

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)]))

51nod 1480 打广告

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

CF82D Two out of Three

基本微积分定理

写在 CSP-S2021 前

20211108 数数 (count)

20211110 漂亮大厨 (cook)

51nod 1480 打广告

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

51nod 1480 打广告

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款