AC鸭的温度墙

题目描述

AC鸭在实验室里看到了一面很长的温度墙，这面墙从左到右一共有 n 个位置。

一开始，每个位置的温度都是 0。

接下来 AC鸭会进行 m 次加热操作。每次操作给出 l,r,v表示把第l个位置到第r个位置的温度都加上上v。

所有操作结束后，AC鸭想知道有多少个位置的温度不小于 k。

输入格式

第一行三个整数 n,m,k表示温度墙长度、操作次数和目标温度。

接下来 m 行，每行三个整数 l,r,v表示一次加热操作。

输出格式

输出一个整数，表示最终温度不小于 k 的位置数量。

样例

输入数据 1

5 2 3 1 3 2 2 5 1

输出数据 1

2

样例解释

两次操作后，温度分别为2 3 3 1 1，其中第 2,3个位置不小于 3。

数据规模

对于 20% 的数据，1≤n,m≤2000。

对于 50% 的数据，1≤n≤25000，1≤m≤25000。

题解

问题分析

给定一个长度为n的数组，初始所有元素为0。进行m次区间加法操作，每次将区间[l, r]内的元素加上v。最后统计数组中不小于k的元素个数。

方法思路

直接模拟每次操作对区间内的元素逐个加v，时间复杂度为O(m*n)，对于n和m达到1e6的情况会超时。需要使用更高效的算法。

差分数组：差分数组能在O(1)时间内完成区间加法操作，最后通过差分数组恢复原数组时只需O(n)时间。

1. 差分数组初始化：创建一个大小为n+2的差分数组diff，初始化为0。
2. 区间加法操作：对于每次操作(l, r, v)，执行diff[l] += v和diff[r+1] -= v。
3. 恢复原数组并统计：遍历差分数组，计算当前前缀和即为原数组的值，统计其中不小于k的个数。

解决代码

#include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vector<int> diff(n + 2, 0); // 差分数组，多开两个空间避免越界 for (int i = 0; i < m; ++i) { int l, r, v; cin >> l >> r >> v; diff[l] += v; if (r + 1 <= n) { diff[r + 1] -= v; } } int current = 0; int count = 0; for (int i = 1; i <= n; ++i) { current += diff[i]; if (current >= k) { ++count; } } cout << count << endl; return 0; }

代码解释

1. 输入处理：使用快速输入方法提高效率，读取温度墙长度n、操作次数m和目标温度k。
2. 差分数组操作：对于每个区间加法操作(l, r, v)，在差分数组的l位置加v，在r+1位置减v，标记区间变化。
3. 恢复原数组并统计：通过差分数组计算前缀和得到每个位置的温度值，同时统计不小于k的温度值个数。
4. 输出结果：输出满足条件的温度值个数。

这种方法利用差分数组将区间加法操作的时间复杂度从O(n)降到O(1)，整体复杂度为O(n + m)，适用于大规模数据。

对于 100% 的数据，1≤n,m≤1000000，1≤l≤r≤n，1≤k,v≤109。