题目分析

本题要求找到一个长度为 $X$ 小时的连续时间段，使得在该时间段内能够为最多的人免除补交的费用，并计算出免除费用的最大值。

关键观察

$1$. 费用免除条件：

一个人在第 $h$ 小时的费用被免除，当且仅当：

$h$ 在区间 $[l_i + t_i, r_i]$ 内（即该人已经用完免费时长 $t_i$ 但仍在疾驰）

第 $h$ 小时时，赛场上疾驰的人数大于 $K$

$2$. 时间线处理：

由于时间范围很大（达到 $10^9$），我们需要使用离散化或事件扫描的方法来处理。

$3$. 人数统计：

对于任意时刻 $t$，我们可以统计：

openAll：当前时刻正在疾驰的总人数

openGood：当前时刻已经用完免费时长但仍需付费的人数

当 openAll > K 时，openGood 中的每个人都需要为当前时刻付费。

算法思路

$1$. 事件定义与扫描：

将每个人的时间区间拆分为三个事件：

起点 $l_i$：开始疾驰，类型为 +1，标记为未用完免费时长

免费结束点 $l_i + t_i$：用完免费时长，类型为 +1，标记为已用完免费时长

终点 $r_i + 1$：结束疾驰，类型为 -1，标记与起点对应

按时间顺序扫描所有事件，维护 openAll 和 openGood 两个计数器。

$2$. 费用贡献计算：

• 当 openAll 变化时，计算免费用能节省的费用贡献：

• 当 openAll 从 $K-1$ 增加到 $K$ 时：从此刻起，openGood 中的每个人开始产生费用贡献

• 当 openAll 从 $K$ 减少到 $K-1$ 时：从此刻起，openGood 中的每个人停止产生费用贡献

• 当 openAll > K 时：每个新进入 openGood 的人开始产生费用贡献，每个离开 openGood 的人停止产生费用贡献

$3$. 差分数组构建：

将费用贡献的变化记录为差分数组 d，其中 d[pos] 表示从时间 pos 开始，单位时间内可节省的费用变化量。

$4$. 前缀和预处理：

对差分数组求前缀和，得到：

prefD[i]：时间点 $d[i][0]$ 之前的总费用率变化量

prefP[i]：时间点 $d[i][0]$ 之前的费用率变化量与时间的加权和

$5$. 滑动窗口计算：

对于每个可能的右端点 $R$，计算窗口 $[R-X, R]$ 内的总节省费用：

其中 $\text{rate}(t)$ 是时间 $t$ 的单位时间节省费用率。

利用前缀和可以快速计算：

其中 $L = R-X+1$。

$6$. 枚举优化：

只需要在差分数组的负变化点（即费用率减少的时刻）检查 $R-1$ 作为右端点，因为最优解一定在费用率变化的边界处。

算法步骤

$1$. 事件收集：

对每个人 $i$：

添加事件 $(l_i, +1, 0)$

如果 $l_i + t_i \le r_i$，添加事件 $(l_i + t_i, +1, 1)$

添加事件 $(r_i + 1, -1, \text{标记})$

$2$. 事件排序与扫描：

按时间排序，时间相同时按类型排序（+1 在 -1 之前）。

扫描过程中维护：

openAll：当前总人数

openGood：当前已用完免费时长的人数

差分数组 d：记录费用率变化

$3$. 前缀和计算：

对差分数组 d 计算两个前缀和数组：

prefD：费用率变化量的前缀和

prefP：费用率变化量 × 时间点的前缀和

$4$. 滑动窗口最大值：

遍历差分数组中的每个负变化点，以该点前一个时间作为右端点候选，计算长度为 $X$ 的窗口内的总节省费用，取最大值。

时间复杂度

事件处理：$O(N \log N)$，用于排序

扫描过程：$O(N)$

滑动窗口计算：$O(N \log N)$，每个候选点使用二分查找

总时间复杂度为 $O(N \log N)$，可以处理 $N \le 10^5$ 的数据规模。

正确性证明

$1$. 事件建模的完备性：

每个人的疾驰过程被精确建模为三个事件，覆盖了从开始疾驰到结束的全部时间段，以及免费时长用完的关键时间点。

$2$. 费用计算的准确性：

只有在同时满足两个条件时才产生费用：

人数超过 $K$

个人已用完免费时长

算法通过维护 openAll 和 openGood 计数器，在适当的时间点更新费用率，确保计算准确。

$3$. 滑动窗口的最优性：

由于费用率是分段常数函数，最优长度为 $X$ 的窗口必然以某个费用率变化点作为边界。因此只需检查这些候选点即可找到全局最优解。

AC代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, x;
    cin >> n >> k >> x;
    vector<array<int, 3>> events;  // {时间, 类型, 标记}
    
    // 收集所有事件
    for (int i = 0; i < n; i++) {
        int l, t, r;
        cin >> l >> t >> r;
        events.push_back({l, +1, 0});  // 开始疾驰
        
        int s = 0;
        int p = l + t;  // 免费时长用完的时间点
        
        if (p < r + 1) {  // 如果免费时长在疾驰结束前用完
            s = 1;
            events.push_back({p, +1, s});  // 进入需付费状态
        }
        
        events.push_back({r + 1, -1, s});  // 结束疾驰
    }
    
    // 事件排序：先按时间，时间相同则+1在前，-1在后
    sort(events.begin(), events.end(), [&](array<int, 3> i, array<int, 3> j) {
        if (i[0] == j[0]) {
            return i[1] < j[1];
        }
        return i[0] < j[0];
    });
    
    // 构建差分数组d，记录费用率变化
    vector<array<int, 2>> d;
    auto Update = [&](int p, int add) {
        if (add == 0) return;
        
        if ((int)d.size() > 0 && d.back()[0] == p) {
            d[(int)d.size() - 1][1] += add;
        } else {
            d.push_back({p, add});
        }
    };
    
    // 扫描事件
    int openGood = 0;  // 已用完免费时长的人数
    int openAll = 0;   // 总人数
    
    for (int i = 0; i < (int)events.size(); i++) {
        int s = events[i][2];
        int v = events[i][1];
        int pos = events[i][0];
        
        if (v == +1) {  // 有人加入
            if (s) {  // 加入的是已用完免费时长的人
                openGood += 1;
                if (openAll >= k) {
                    Update(pos, +1);  // 如果总人数已超K，此人立即开始产生费用
                }
            } else {  // 加入的是未用完免费时长的人
                openAll += 1;
                if (openAll == k) {
                    Update(pos, +openGood);  // 总人数刚达到K，所有已用完免费时长的人开始产生费用
                }
            }
        } else {  // 有人离开
            if (s) {  // 离开的是已用完免费时长的人
                openGood -= 1;
                if (openAll >= k) {
                    Update(pos, -1);  // 如果总人数超K，此人停止产生费用
                }
            }
            
            openAll -= 1;
            
            if (openAll == k - 1) {
                Update(pos, -openGood);  // 总人数降到K以下，所有已用完免费时长的人停止产生费用
            }
        }
    }
    
    const int inf = 1000000000;
    int len = (int)d.size();
    
    // 计算前缀和
    vector<long long> prefD(len);  // 费用率变化量的前缀和
    vector<long long> prefP(len);  // 费用率变化量×时间点的前缀和
    
    for (int i = 0; i < len; i++) {
        if (i > 0) {
            prefD[i] += prefD[i - 1];
            prefP[i] += prefP[i - 1];
        }
        prefD[i] += d[i][1];
        prefP[i] += 1LL * d[i][0] * d[i][1];
    }
    
    // 计算以ptRight为右端点，长度为x的窗口内的总节省费用
    auto Calc = [&](int ptRight) {
        int L = ptRight - x + 1;
        auto ptr0 = lower_bound(d.begin(), d.end(), array<int,2>({L, inf})) - d.begin();
        auto ptr1 = lower_bound(d.begin(), d.end(), array<int,2>({ptRight, inf})) - d.begin();
        ptr1 -= 1;
        
        if (ptr1 < 0) return 0LL;
        
        // 计算[L, ptRight]区间内的积分
        long long ret = 1LL * (ptRight + 1) * 
                       (prefD[ptr1] - (ptr0 > 0 ? prefD[ptr0 - 1] : 0LL)) -
                       (prefP[ptr1] - (ptr0 > 0 ? prefP[ptr0 - 1] : 0LL));
        
        if (ptr0 > 0) {
            ret += 1LL * prefD[ptr0 - 1] * x;  // 处理L之前的常数部分
        }
        
        return ret;
    };
    
    // 寻找最大值
    long long res = 0;
    for (int i = 0; i < (int)d.size(); i++) {
        int pos = d[i][0];
        int c = d[i][1];
        
        if (c < 0) {  // 只在费用率减少的点检查
            res = max(res, Calc(pos - 1));
        }
    }
    
    cout << res << '\n';
    return 0;
}