51nod 1480 打广告

博主： tony102
发布时间：2021 年 09 月 20 日
1376 次浏览
暂无评论
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技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rlenitkthe
真好呢
暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了

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)

3D Gaussian Splatting for Real-Time Radiance Field Rendering

Luogu1891 疯狂 LCM

20211110 漂亮大厨 (cook)

原神《稻妻》OST 指弹（片段）

Indoor Gaussian Splatting Paper Report 1

51nod 1480 打广告

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

51nod 1480 打广告

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