解题思路

1. 将问题转化

把每株花对应为一个等长区间，定义覆盖计数 $c(x)$ 为时刻 $x$ 被多少区间覆盖。 我们关心的量为

$$S=\sum_x [c(x)=1],$$

即被恰好 1 个区间覆盖的总长度。

若把某一株 $i$ 的区间移走（临时删除），对 $S$ 的影响：

• 把原来 $i$ 独占 的部分（记为 $uni_i$）从 1 变为 0，$\Delta=-uni_i$；
• 把原来 恰好两株覆盖且其中一株是 $i$ 的部分（记为 $two_i$）从 2 变为 1，$\Delta=+two_i$；
• 对覆盖数 ≥3 的部分无影响。

所以“删除 $i$”后得到 $S' = S - uni_i + two_i$。

再次把 $i$ 放回去：我们可以把它移动到任意位置。若把它放到与其它区间完全不相交的地方，则新增贡献 = 区间长度 $m$。 （题面允许改成任意正整数，因此永远能把区间放到一个“远离所有区间”的位置。）

于是若选择第 $i$ 株去改，最终

$$S_{\text{final}} = S - uni_i + two_i + m = S + m + (two_i - uni_i).$$

显然应选使 $two_i - uni_i$ 最大的 $i$。另外，我们也可以“不真正移动”，使答案至少为当前的 $S$。因此

$$\boxed{\text{Ans}=\max\Big(S,\ S+m+\max_i(two_i-uni_i)\Big)}.$$

问题归约为：用一次扫描计算

• 总的 $S$；
• 每个区间 $i$ 的 $uni_i$（它独占的长度）与 $two_i$（它处在“恰好两株覆盖”时的长度）。

2. 扫描线 + 事件（坐标压缩）

时刻范围可能很大，但区间端点只有 $O(n)$ 个。对所有端点做坐标压缩并用“进入/离开事件”扫描：

• 对区间 $[l,r]$ 建两个事件：在 $l$ 处加入 $i$；在 $r+1$ 处移除 $i$（把闭区间转成半开 $[l, r+1)$ 便于处理）。

• 将所有事件时刻升序，维护当前活跃集合 act（存活区间的编号）。

• 若相邻压缩点 $[x, next)$ 之间长度为 len = next - x，则：

  • |act|==1：记唯一编号为 id，令 uni[id]+=len 且 S+=len；
  • |act|==2：设为 a,b，令 two[a]+=len，two[b]+=len；
  • 其它情况忽略。

• 时间复杂度 $O(n\log n)$（集合增删取元素），空间 $O(n)$。

这就是标准的扫描线算法。

复杂度

• 坐标压缩与事件排序：$O(n\log n)$；
• 扫描线：每事件一次插入/删除，$O(n\log n)$；
• 总复杂度：$O(n\log n)$，空间 $O(n)$。

代码

Python

import sys

def solve_one(n, m, ts):
    # 构造闭区间 [l, r]，并准备 r+1 作为离开事件
    L, R = [], []
    pts = []
    for i, t in enumerate(ts):
        l = t
        r = t + m - 1
        L.append(l)
        R.append(r)
        pts.append(l)
        pts.append(r + 1)

    # 坐标压缩
    xs = sorted(set(pts))
    idx = {x:i for i, x in enumerate(xs)}
    k = len(xs)

    # 事件：在压缩坐标 pos 处的进入/离开列表
    add = [[] for _ in range(k)]
    rem = [[] for _ in range(k)]
    for i in range(n):
        add[idx[L[i]]].append(i)
        rem[idx[R[i] + 1]].append(i)

    # 扫描线
    import bisect
    act = set()           # 当前活跃区间的编号集合
    uni = [0] * n         # 每个区间独占长度
    two = [0] * n         # 每个区间处在“恰好两株”时的长度
    S = 0                 # 全局恰好一株的长度

    for p in range(k - 1):
        # 先处理在 xs[p] 处的进入事件
        for i in add[p]:
            act.add(i)
        length = xs[p + 1] - xs[p]
        if length > 0:
            if len(act) == 1:
                i = next(iter(act))
                uni[i] += length
                S += length
            elif len(act) == 2:
                it = iter(act)
                a = next(it); b = next(it)
                two[a] += length
                two[b] += length
        # 区间在 r+1 处离开
        for i in rem[p + 1]:
            if i in act:
                act.remove(i)

    # 计算答案：max(S, S + m + max(two[i]-uni[i]))
    best = max((two[i] - uni[i] for i in range(n)), default=-(10**18))
    return max(S, S + m + best)

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    t = int(next(it))
    out = []
    for _ in range(t):
        n = int(next(it)); m = int(next(it))
        ts = [int(next(it)) for _ in range(n)]
        out.append(str(solve_one(n, m, ts)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static long solveOne(int n, int m, int[] ts) {
        int[] L = new int[n], R = new int[n];
        ArrayList<Integer> pts = new ArrayList<>(2 * n);
        for (int i = 0; i < n; i++) {
            L[i] = ts[i];
            R[i] = ts[i] + m - 1;
            pts.add(L[i]);
            pts.add(R[i] + 1);     // 半开区间的右端
        }
        // 坐标压缩
        Collections.sort(pts);
        ArrayList<Integer> xs = new ArrayList<>();
        for (int x : pts) if (xs.isEmpty() || xs.get(xs.size()-1) != x) xs.add(x);
        int k = xs.size();
        HashMap<Integer, Integer> idx = new HashMap<>(k * 2);
        for (int i = 0; i < k; i++) idx.put(xs.get(i), i);

        ArrayList<Integer>[] add = new ArrayList[k];
        ArrayList<Integer>[] rem = new ArrayList[k];
        for (int i = 0; i < k; i++) { add[i] = new ArrayList<>(); rem[i] = new ArrayList<>(); }
        for (int i = 0; i < n; i++) {
            add[idx.get(L[i])].add(i);
            rem[idx.get(R[i] + 1)].add(i);
        }

        long[] uni = new long[n];
        long[] two = new long[n];
        long S = 0;

        // 使用 LinkedHashSet 保证能取到首个元素（任意一个即可）
        HashSet<Integer> act = new HashSet<>();
        for (int p = 0; p < k - 1; p++) {
            // 进入
            for (int id : add[p]) act.add(id);
            long len = (long) xs.get(p + 1) - xs.get(p);
            if (len > 0) {
                if (act.size() == 1) {
                    int id = act.iterator().next();
                    uni[id] += len;
                    S += len;
                } else if (act.size() == 2) {
                    Iterator<Integer> it = act.iterator();
                    int a = it.next(), b = it.next();
                    two[a] += len;
                    two[b] += len;
                }
            }
            // 离开
            for (int id : rem[p + 1]) act.remove(id);
        }

        long best = Long.MIN_VALUE / 4;
        for (int i = 0; i < n; i++) best = Math.max(best, two[i] - uni[i]);
        return Math.max(S, S + m + best);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        for (int tc = 0; tc < T; tc++) {
            String[] nm = br.readLine().trim().split("\\s+");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            String[] tsStr = br.readLine().trim().split("\\s+");
            int[] ts = new int[n];
            for (int i = 0; i < n; i++) ts[i] = Integer.parseInt(tsStr[i]);
            long ans = solveOne(n, m, ts);
            out.append(ans).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, m; 
        cin >> n >> m;
        vector<long long> t(n);
        for (int i = 0; i < n; ++i) cin >> t[i];

        vector<long long> L(n), R(n);
        vector<long long> pts; pts.reserve(2*n);
        for (int i = 0; i < n; ++i) {
            L[i] = t[i];
            R[i] = t[i] + m - 1;
            pts.push_back(L[i]);
            pts.push_back(R[i] + 1); // 半开右端
        }
        sort(pts.begin(), pts.end());
        pts.erase(unique(pts.begin(), pts.end()), pts.end());
        int k = (int)pts.size();

        vector<vector<int>> add(k), rem(k);
        auto get_idx = [&](long long x)->int {
            return (int)(lower_bound(pts.begin(), pts.end(), x) - pts.begin());
        };
        for (int i = 0; i < n; ++i) {
            add[get_idx(L[i])].push_back(i);
            rem[get_idx(R[i] + 1)].push_back(i);
        }

        vector<long long> uni(n, 0), two(n, 0);
        long long S = 0;
        unordered_set<int> act; act.reserve(n*2+10);

        for (int p = 0; p + 1 < k; ++p) {
            for (int id : add[p]) act.insert(id); // 进入
            long long len = pts[p+1] - pts[p];
            if (len > 0) {
                if (act.size() == 1) {
                    int id = *act.begin();
                    uni[id] += len; S += len;
                } else if (act.size() == 2) {
                    auto it = act.begin();
                    int a = *it; ++it; int b = *it;
                    two[a] += len; two[b] += len;
                }
            }
            for (int id : rem[p+1]) act.erase(id); // 离开
        }

        long long best = LLONG_MIN/4;
        for (int i = 0; i < n; ++i) best = max(best, two[i] - uni[i]);
        long long ans = max(S, S + (long long)m + best);
        cout << ans << "\n";
    }
    return 0;
}

题目内容

昙花是一种很美丽的花；可惜的是，昙花开花的时间非常短暂，所以才有“昙花一现”之说，人们常说，目睹昙花一现，意味着好的事情即将发生。

小明是一位大魔法师，他种植了 $n$ 株昙花，并预知了这些昙花开花的时间 $t_1,t_2,…,t_n$，每一株昙花只会开花 $m$ 秒，$m$ 是一个固定的数值。也就是说，第 $i$ 株昙花将会在 $[t_i,t_i+m-1]$ 开花。

小明想让自己欣赏昙花开花的时间尽可能长。但是，小明不满足于看两株及以上的昙花开花，他认为那样太过艳丽，有失风采。也就是说，小明想让恰有一株昙花开花的时刻尽可能多。

作为大魔法师，小明可以施展至多一次魔法：他可以选定任意一株昙花，并将这株昙花的开花时间 $t_i$ 修改成任意正整数，请问，小明最多能让恰有一株昙花开花的时间变为多久？

输入描述

本题中，单个测试用例包含多组数据。

第一行一个正整数 $T$ ，表示数据组数。

对于每一组数据：

第一行两个正整数 $n$ 和 $m$

第二行 $n$ 个正整数，表示 $t_1,t_2,...,t_n$ 。

$1≤\sum n≤2*10^5,1≤m,t_i≤5*n,1≤T≤1000$

注意，小明施展魔法时可以将 $t_i$ 修改成任意正整数，不受 $t_i≤5*n$ 的约束。

输出描述

输出 $T$ 行，每行一个非负整数，表示恰有一株昙花开花的最大时刻数。

样例1

输入

2
4 10
1 3 12 20
5 5
2 1 10 3 11

输出

36
12

说明

第一组样例的解释如下：

施展魔法前，四株昙花的开花时间段分别为 $[1,10],[3,12],[12,21]$ 和 $[20,29]$ 。

恰有一株昙花开花的时间段有 $[1,2],[11,11],[13,19]$ 和 $[22,29]$ ，时刻数为 $2+1+7+8=18$ 。

小明可以施展魔法，将 $t_2$ 修改为 $30$ 。

施展魔法后，四株昙花的开花时间段分别为 $[1,10],[30,39],[12,21]$ 和 $[20,29]$ 。

恰有一颗昙花开花的时间段有 $[1,10],[12,19],[22,29]$ 和 $[30,39]$ ，时刻数为 $10+8+10=36$ 。

可以证明没有更优的方案。