精华帖子

[题目链接](https://www.nowcoder.com/practice/708f80899ad04b3a8539d93b1690cd4d)

思路

帖子编号为 $0$ 到 $n$ ，共有 $m$ 个不重叠的精华区间（左闭右开 $[l_i, r_i)$ ），要找一段连续 $k$ 个帖子组成的窗口，使其中精华帖子数量最多。

关键观察：最优窗口的端点

$n$ 可达 $10^9$ ，不可能枚举每个起点。但精华区间只有 $m$ 个，最优窗口的位置一定与某个精华区间的端点对齐——要么窗口左端恰好是某个区间的左端，要么窗口右端恰好是某个区间的右端。

直觉上，如果窗口的两个端点都没有与任何精华区间的端点对齐，那么可以平移窗口使其对齐而不减少覆盖量。

因此，只需枚举 $O(m)$ 个候选起点。

快速计算窗口覆盖量

将所有区间转为闭区间 $[l_i, r_i - 1]$ 并排序。对区间长度做前缀和 $\text{prefix}[i]$ 。

给定窗口 $[L, L+k-1]$ ，用二分查找找出与窗口有交集的区间范围 $[\text{left\_idx}, \text{right\_idx}]$ ：

$\text{left\_idx}$ ：第一个满足 $r_i \geq L$ 的区间
$\text{right\_idx}$ ：最后一个满足 $l_i \leq L+k-1$ 的区间

中间完全被窗口覆盖的区间长度之和可以用前缀和 $O(1)$ 得到，再减去左右两端可能超出窗口的部分即可。

算法流程

读入区间，将右端点减 1 变为闭区间，按左端点排序。
构建区间长度的前缀和数组。
枚举每个区间 $i$ ，分别尝试以 $l_i$ 为窗口左端、以 $r_i$ 为窗口右端，调用 calc 计算覆盖量。
取所有候选中的最大值。

样例演示

$n = 5$ ，精华区间 $[1,2)$ 和 $[3,5)$ ， $k = 3$ 。

转为闭区间： $[1,1]$ 和 $[3,4]$ ，精华帖子为 $\{1, 3, 4\}$ 。

窗口左端 = 1：覆盖 $[1,3]$ ，精华 = $\{1,3\}$ = 2 个
窗口右端 = 1（左端 = -1 -> 0）：覆盖 $[0,2]$ ，精华 = $\{1\}$ = 1 个
窗口左端 = 3：覆盖 $[3,5]$ ，精华 = $\{3,4\}$ = 2 个
窗口右端 = 4（左端 = 2）：覆盖 $[2,4]$ ，精华 = $\{3,4\}$ = 2 个

最大值为 2。

复杂度

时间复杂度： $O(m \log m)$ ，排序 $O(m \log m)$ ，每次 calc 两次二分 $O(\log m)$ ，共 $O(m)$ 次调用。
空间复杂度： $O(m)$ ，存储区间和前缀和。

代码

C++
Java
Python3
JavaScript

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

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

    long long n, m, k;
    cin >> n >> m >> k;

    vector<pair<long long,long long>> seg(m);
    for(int i = 0; i < m; i++){
        cin >> seg[i].first >> seg[i].second;
        seg[i].second--;
    }
    sort(seg.begin(), seg.end());

    vector<long long> prefix(m+1, 0);
    for(int i = 0; i < m; i++){
        prefix[i+1] = prefix[i] + (seg[i].second - seg[i].first + 1);
    }

    auto calc = [&](long long L) -> long long {
        long long R = L + k - 1;
        int lo = 0, hi = m - 1, left_idx = m;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(seg[mid].second >= L){ left_idx = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        lo = 0; hi = m - 1;
        int right_idx = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(seg[mid].first <= R){ right_idx = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        if(left_idx > right_idx) return 0;
        long long total = prefix[right_idx+1] - prefix[left_idx];
        if(seg[left_idx].first < L) total -= (L - seg[left_idx].first);
        if(seg[right_idx].second > R) total -= (seg[right_idx].second - R);
        return total;
    };

    long long ans = 0;
    for(int i = 0; i < m; i++){
        ans = max(ans, calc(seg[i].first));
        long long L = seg[i].second - k + 1;
        if(L < 0) L = 0;
        ans = max(ans, calc(L));
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static long[][] seg;
    static long[] prefix;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());

        seg = new long[m][2];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            seg[i][0] = Long.parseLong(st.nextToken());
            seg[i][1] = Long.parseLong(st.nextToken()) - 1;
        }
        Arrays.sort(seg, (a, b) -> Long.compare(a[0], b[0]));

        prefix = new long[m + 1];
        for (int i = 0; i < m; i++) {
            prefix[i + 1] = prefix[i] + (seg[i][1] - seg[i][0] + 1);
        }

        long ans = 0;
        for (int i = 0; i < m; i++) {
            ans = Math.max(ans, calc(m, k, seg[i][0]));
            long L = seg[i][1] - k + 1;
            if (L < 0) L = 0;
            ans = Math.max(ans, calc(m, k, L));
        }
        System.out.println(ans);
    }

    static long calc(int m, long k, long L) {
        long R = L + k - 1;
        int lo = 0, hi = m - 1, leftIdx = m;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (seg[mid][1] >= L) { leftIdx = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        lo = 0; hi = m - 1;
        int rightIdx = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (seg[mid][0] <= R) { rightIdx = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        if (leftIdx > rightIdx) return 0;
        long total = prefix[rightIdx + 1] - prefix[leftIdx];
        if (seg[leftIdx][0] < L) total -= (L - seg[leftIdx][0]);
        if (seg[rightIdx][1] > R) total -= (seg[rightIdx][1] - R);
        return total;
    }
}

import sys
from bisect import bisect_left, bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    m = int(input_data[idx]); idx += 1
    k = int(input_data[idx]); idx += 1

    seg = []
    for i in range(m):
        l = int(input_data[idx]); idx += 1
        r = int(input_data[idx]); idx += 1
        seg.append((l, r - 1))
    seg.sort()

    lefts = [s[0] for s in seg]
    rights = [s[1] for s in seg]

    prefix = [0] * (m + 1)
    for i in range(m):
        prefix[i + 1] = prefix[i] + (seg[i][1] - seg[i][0] + 1)

    def calc(L):
        R = L + k - 1
        left_idx = bisect_left(rights, L)
        right_idx = bisect_right(lefts, R) - 1
        if left_idx > right_idx:
            return 0
        total = prefix[right_idx + 1] - prefix[left_idx]
        if seg[left_idx][0] < L:
            total -= (L - seg[left_idx][0])
        if seg[right_idx][1] > R:
            total -= (seg[right_idx][1] - R)
        return total

    ans = 0
    for i in range(m):
        ans = max(ans, calc(seg[i][0]))
        L = seg[i][1] - k + 1
        if L < 0:
            L = 0
        ans = max(ans, calc(L))

    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m, k] = lines[0].split(' ').map(Number);
    const seg = [];
    for (let i = 0; i < m; i++) {
        const parts = lines[i + 1].split(' ').map(Number);
        seg.push([parts[0], parts[1] - 1]);
    }
    seg.sort((a, b) => a[0] - b[0]);

    const lefts = seg.map(s => s[0]);
    const rights = seg.map(s => s[1]);

    const prefix = new Array(m + 1).fill(0);
    for (let i = 0; i < m; i++) {
        prefix[i + 1] = prefix[i] + (seg[i][1] - seg[i][0] + 1);
    }

    function bisectLeft(arr, val) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    function bisectRight(arr, val) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] <= val) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    function calc(L) {
        const R = L + k - 1;
        const leftIdx = bisectLeft(rights, L);
        const rightIdx = bisectRight(lefts, R) - 1;
        if (leftIdx > rightIdx) return 0;
        let total = prefix[rightIdx + 1] - prefix[leftIdx];
        if (seg[leftIdx][0] < L) total -= (L - seg[leftIdx][0]);
        if (seg[rightIdx][1] > R) total -= (seg[rightIdx][1] - R);
        return total;
    }

    let ans = 0;
    for (let i = 0; i < m; i++) {
        ans = Math.max(ans, calc(seg[i][0]));
        let L = seg[i][1] - k + 1;
        if (L < 0) L = 0;
        ans = Math.max(ans, calc(L));
    }

    console.log(ans);
});