题解 B4047：校门外的施工

yummy · 2024-10-21 01:24:05 · 题解

本题考查数组的综合应用，idea 来源就是在 校门外的树 基础上，加入了更多下标范围 \pm 1 的考查。

考虑用 tr[i] 表示第 i 棵树是否被破坏，gr[i] 表示第 i,i+1 棵树之间的草坪是否被破坏。（这里建议写一个注释，否则你可能会忘记 gr[i] 表示 i,i+1 之间的草坪还是 i,i-1 之间的草坪）。

接下来分类讨论一下每种操作分别对树和草坪产生了什么影响：

• 1 l r 破坏了第 l+1\sim r-1 棵树。
• 2 l r 破坏了第 l\sim r 棵树。
• 无论是 1 l r 还是 2 l r，都破坏了 l\sim l+1,l+1\sim l+2,\ldots, r-1\sim r 这些草坪。注意这对应 gr[l] 到 gr[r-1]。

用一个循环嵌套（外层表示这是第几个施工，内层对产生的破坏进行记录），最后统计剩下的树和草坪数量即可。

注意，统计总数时，树看的是 tr[1],...,tr[m]，然而草坪看的是 gr[1],...,gr[m-1]。