题解 | #小红的区间构造#

自用

D-小红的最佳区间_牛客周赛 Round 143

    我们假设[L, L + k]与[l ,r]区间相交，则有

        · L <= r

        · L + k >= l

    即 l - k <= L <= r。

    故与[l, r]区间相交的[L, L + k]区间的条件是 l - k <= L <= r。

    换句话来说，若l - k <= L <= r，则其会为区间[l, r]的每个点做出一个贡献。

    问最多有多少个给定区间能够与她选择的区间 [L,L+k] 相交，即[1, max]中哪个点的贡献最多。

    对[l ,r]做出贡献是区间修改，同时由于max可能会很大，而所用到的点不会全部覆盖，故进行离散化。

    写完发现其实就是扫描线。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define endl '\n'
const int N = 1e6;
const ll mod = 1e9 + 7;
const int M = 1e8+10;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<ll> l(n), r(n);
    vector<ll> all;
    all.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
        ll a = l[i] - k;
        ll b = r[i];
        all.push_back(a);
        all.push_back(b + 1);
    }

    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    int m = all.size();
    vector<int> diff(m + 1, 0);

    for (int i = 0; i < n; ++i) {
        ll a = l[i] - k;
        ll b = r[i];
        int idx_a = lower_bound(all.begin(), all.end(), a) - all.begin();
        int idx_b = lower_bound(all.begin(), all.end(), b + 1) - all.begin();
        diff[idx_a] += 1;
        diff[idx_b] -= 1;
    }

    int cur = 0, ans = 0;
    for (int i = 0; i < m; ++i) {
        cur += diff[i];
        ans = max(ans, cur);
    }

    cout << ans << endl;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);

    int T = 1;
    // cin >> T;
    while(T--) solve();
    return 0;
}