记录151#includebits/stdc.h // 引入万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间std const int N1e65; // 定义常量N表示油漆罐数量的最大范围10^6级别 // 核心数组二维差分数组。 // diff[颜色][位置]记录每种颜色在对应位置的差分标记。 // 第一维 1,2,3 分别代表黄、蓝、红三种颜料。 int diff[4][N]; int main(){ // 优化输入输出流的效率防止在百万级数据量下超时 ios::sync_with_stdio(false); cin.tie(0); int n,m; // n: 油漆罐总数, m: 调色专家的操作次数 cinnm; // ---------- 第一阶段差分标记区间修改 O(1)---------- // 循环读取 m 次操作将“区间加颜料”转化为“两个端点的差分标记” for(int i1;im;i){ int l,r,k; // l, r: 操作的油漆罐区间 [l, r] // k: 加入的颜料种类 (1黄色, 2蓝色, 3红色) cinlrk; diff[k][l]; // 在区间起点 l 处该颜色的差分 1表示从这里开始有这种颜色 diff[k][r1]--; // 在区间终点后一位 r1 处该颜色的差分 -1表示从这里开始抵消这种颜色 } int ans0; // 定义变量 ans用来记录最终有多少罐油漆变成了绿色 // sum 数组记录当前遍历到的油漆罐中三种颜色的“前缀和”即真实叠加次数 // sum[1]: 黄色叠加次数, sum[2]: 蓝色叠加次数, sum[3]: 红色叠加次数 int sum[4]{0}; // ---------- 第二阶段前缀和还原与统计单点查询 O(1)---------- // 从左到右遍历每一个油漆罐1 到 n for(int i1;in;i){ // 对三种颜色分别求前缀和。 // 原理差分数组的前缀和 原数组的真实值。 // 通过累加我们就能知道第 i 罐油漆里到底叠加了几次黄、蓝、红。 for(int j1;j3;j){ sum[j]diff[j][i]; } // ---------- 核心逻辑判断是否为绿色 ---------- // 根据题目规则绿色的形成条件是 // 1. 至少叠加了黄色 (sum[1] 0) // 2. 至少叠加了蓝色 (sum[2] 0) // 3. 绝对不能有红色 (sum[3] 0) // (注如果有红色黄蓝红会变成棕色如果只有黄或只有蓝则是黄色或蓝色) if(sum[1]0sum[2]0sum[3]0){ ans; // 满足绿色条件答案加 1 } } coutans\n; // 输出最终变成绿色的油漆罐数量 return 0; // 程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P9094前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的差分Difference Array与前缀和应用问题。问题转化与数据规模分析题目给出了 nn 罐油漆和 mm 次操作每次操作是对一个区间 [l,r][l,r] 内的所有油漆加入某种颜料。由于 nn 和 mm 的最大值都达到了 10^6 如果采用暴力的方法每次操作都遍历区间内的每一个罐子时间复杂度将达到 O(n×m)即 10^12 级别这必然会导致超时。因此我们需要一种能将“区间修改”优化为 O(1) 时间复杂度的算法。算法设计差分 前缀和还原差分标记差分是处理区间修改的神器。对于区间 [l,r] 的修改我们只需要在差分数组的 ll 位置加上修改值在 r1 位置减去修改值。这样 m 次区间修改操作的总时间复杂度就降为了 O(m) 。前缀和还原当我们完成了所有的差分标记后对差分数组求前缀和就能还原出每一个油漆罐上各种颜料被添加的真实总次数。颜色判定根据题目给出的混合规则绿色的形成条件非常明确必须同时包含黄色和蓝色且绝对不能包含红色。我们在还原出每个罐子的颜料叠加次数后直接判断即可。代码分块详细解释1. 头文件、常量与核心数组定义#includebits/stdc.h using namespace std; const int N1e65; // 核心数组二维差分数组。 // diff[颜色][位置]记录每种颜色在对应位置的差分标记。 // 第一维 1,2,3 分别代表黄、蓝、红三种颜料。 int diff[4][N];详细分析因为颜料有三种黄、蓝、红且我们需要分别记录每种颜料在每个位置的叠加情况所以使用了一个二维数组diff[4][N]作为差分数组。数组大小开到 10651065 以容纳题目中的最大数据规模。2. 第一阶段差分标记区间修改 O(1)int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cinnm; // 循环读取 m 次操作将“区间加颜料”转化为“两个端点的差分标记” for(int i1;im;i){ int l,r,k; cinlrk; diff[k][l]; // 在区间起点 l 处该颜色的差分 1 diff[k][r1]--; // 在区间终点后一位 r1 处该颜色的差分 -1 }详细分析这部分是差分数组的核心应用。对于第 ii 次操作向 [l,r] 区间加入颜料 k我们不需要真的去遍历 [l,r] 中的每一个罐子而是直接在diff[k][l]处加 1表示从 ll 开始颜料 k 的数量增加了 1在diff[k][r1]处减 1表示从 r1 开始颜料 k 增加的效果被抵消了。这样无论区间 [l,r][l,r] 有多长我们都只进行了两次数组操作将区间修改的时间复杂度完美降到了 O(1) 。3. 第二阶段前缀和还原与绿色判定int ans0; // sum 数组记录当前遍历到的油漆罐中三种颜色的“前缀和”即真实叠加次数 int sum[4]{0}; // 从左到右遍历每一个油漆罐1 到 n for(int i1;in;i){ // 对三种颜色分别求前缀和。 for(int j1;j3;j){ sum[j]diff[j][i]; } // ---------- 核心逻辑判断是否为绿色 ---------- // 根据题目规则绿色的形成条件是 // 1. 至少叠加了黄色 (sum[1] 0) // 2. 至少叠加了蓝色 (sum[2] 0) // 3. 绝对不能有红色 (sum[3] 0) if(sum[1]0sum[2]0sum[3]0){ ans; } } coutans\n; return 0; }详细分析这是代码的收尾与统计阶段。前缀和还原我们定义了一个sum数组用来实时记录当前遍历到的油漆罐上各种颜料的真实叠加次数。在遍历到第 ii 个罐子时执行sum[j] diff[j][i]这就是差分数组还原为原数组的过程。此时sum[1]、sum[2]、sum[3]分别代表了第 ii 罐油漆上黄色、蓝色、红色被添加的总次数。颜色判定根据题目给出的混合表绿色的形成条件是“黄色 蓝色”。这意味着当前罐子必须至少被添加过一次黄色sum[1] 0和至少一次蓝色sum[2] 0。同时必须确保没有红色sum[3] 0因为一旦有红色黄蓝红就会变成棕色。满足这三个条件答案ans就加 1。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点差分标记diff[k][l],diff[k][r1]--将区间 [l,r][l,r] 的修改转化为两个端点的操作将每次区间修改的时间复杂度从 O(n)O(n) 降为 O(1)O(1) 防止 106106 级别数据超时前缀和还原sum[j] diff[j][i]通过累加差分数组还原出每个罐子的真实颜料叠加次数将分散的差分标记整合为每个油漆罐的最终状态为颜色判定提供数据颜色判定sum[1]0 sum[2]0 sum[3]0根据混合规则判断当前罐子是否为绿色准确过滤出“有黄有蓝且无红”的油漆罐排除棕色、黄色、蓝色等干扰项全局计数ans累加满足绿色条件的油漆罐数量统计最终答案IO加速ios::sync_with_stdio(false)关闭标准流同步应对 106106 级别的大量输入输出防止 IO 瓶颈导致超时