AC鸭的温度墙

题目描述AC鸭在实验室里看到了一面很长的温度墙这面墙从左到右一共有 n 个位置。一开始每个位置的温度都是 0。接下来 AC鸭会进行 m 次加热操作。每次操作给出 l,r,v表示把第l个位置到第r个位置的温度都加上上v。所有操作结束后AC鸭想知道有多少个位置的温度不小于 k。输入格式第一行三个整数 n,m,k表示温度墙长度、操作次数和目标温度。接下来 m 行每行三个整数 l,r,v表示一次加热操作。输出格式输出一个整数表示最终温度不小于 k 的位置数量。样例输入数据 15 2 3 1 3 2 2 5 1输出数据 12样例解释两次操作后温度分别为2 3 3 1 1其中第 2,3个位置不小于 3。数据规模对于 20% 的数据1≤n,m≤2000。对于 50% 的数据1≤n≤250001≤m≤25000。题解问题分析给定一个长度为n的数组初始所有元素为0。进行m次区间加法操作每次将区间[l, r]内的元素加上v。最后统计数组中不小于k的元素个数。方法思路直接模拟每次操作对区间内的元素逐个加v时间复杂度为O(m*n)对于n和m达到1e6的情况会超时。需要使用更高效的算法。差分数组差分数组能在O(1)时间内完成区间加法操作最后通过差分数组恢复原数组时只需O(n)时间。差分数组初始化创建一个大小为n2的差分数组diff初始化为0。区间加法操作对于每次操作(l, r, v)执行diff[l] v和diff[r1] - v。恢复原数组并统计遍历差分数组计算当前前缀和即为原数组的值统计其中不小于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; vectorint 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; }代码解释输入处理使用快速输入方法提高效率读取温度墙长度n、操作次数m和目标温度k。差分数组操作对于每个区间加法操作(l, r, v)在差分数组的l位置加v在r1位置减v标记区间变化。恢复原数组并统计通过差分数组计算前缀和得到每个位置的温度值同时统计不小于k的温度值个数。输出结果输出满足条件的温度值个数。这种方法利用差分数组将区间加法操作的时间复杂度从O(n)降到O(1)整体复杂度为O(n m)适用于大规模数据。对于 100% 的数据1≤n,m≤10000001≤l≤r≤n1≤k,v≤109。