思维+差分，CF 1884C - Medium Design

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1884C - Medium Design

---

二、解题报告

1、思路分析

考虑 最大值 和 最小值的位置 mai, mii

对于 一个 包含 mai 的线段，我们选择：

如果 该线段包含 mii，答案不会变大

如果 该线段不包含 mii，答案会 + 1

也就是说，对于所有的包含 mai 的线段，我们拿进来不会使得答案变差

同时包含 mai，mii 的线段我们可以不拿

那么我们说明 最优解 的 mii 一定在 两端

我们按照 mii 在左端 和 右端 的情况分别计算，求最值即可

以mii = 0为例，我们对于所有左端点不为0的线段按左右端点双关键字排序，跑差分

维护被覆盖次数最多的点的次数，维护最值即可

2、复杂度

时间复杂度： O(nlogn)空间复杂度：O(n)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {int n, m;std::cin >> n >> m;std::vector<int> l(n), r(n);for (int i = 0; i < n; ++ i) {std::cin >> l[i] >> r[i];-- l[i];}std::vector<std::pair<int, int>> segs;for (int i = 0; i < n; ++ i) {if (l[i] > 0) {segs.emplace_back(l[i], 1);segs.emplace_back(r[i], -1);}}int ans = 0;int cur = 0, lst = 0;std::ranges::sort(segs);for (auto &[x, y] : segs) {if (x > lst) {ans = std::max(ans, cur);}lst = x;       cur += y;}if (m > lst) {ans = std::max(ans, cur);}segs.clear();for (int i = 0; i < n; ++ i) {if (r[i] < m) {segs.emplace_back(l[i], 1);segs.emplace_back(r[i], -1);}}std::ranges::sort(segs);cur = 0, lst = 0;for (auto &[x, y] : segs) {if (x > lst) {ans = std::max(ans, cur);}lst = x;cur += y;}if (m > lst) {ans = std::max(ans, cur);}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint add = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - add << '\n';
#endifreturn 0;
}